\documentclass[a4paper]{report} 
\usepackage[dutch]{babel}
\usepackage{graphicx}
\usepackage{subfig}
\usepackage{wrapfig}
\usepackage{ctable}
\usepackage{color}
\usepackage{listings}
\lstset{%
language=C++,%
basicstyle=\footnotesize,%
numbers=left,%
numberstyle=\footnotesize,%
stepnumber=1,%
numbersep=5pt,%
backgroundcolor=\color{white},%
showspaces=false,%
showstringspaces=false,%
showtabs=false,%
frame=single,%
tabsize=2,%
captionpos=b,%
breaklines=true,%
breakatwhitespace=false,%
escapeinside={\%}{)}, %
mathescape={true} %
}
\author{Ruben van Haaster\\\\Promotor: Marc Gyssens\\\\Begeleider: Bart Moelans}
\title{Visualiseren van Graafalgoritmen}
\date{}

\newcommand{\class}[1]{\texttt{#1}}
\newcommand{\function}[1]{\texttt{\footnotesize#1}}

\usepackage{pdfpages}
\usepackage{newclude}

\begin{document}
% \maketitle
\input{./title.tex}
\newpage

\begin{center}
{\textbf {\large Woord Vooraf} }\\[.5cm]
\end{center}

\noindent Dit verslag maakt deel uit van mijn bachelorproef over het visualizeren van graafalgoritmen, voorgedragen tot het behalen van de graad van bachelor in de informatica aan de Universiteit Hasselt. In dit verslag bespreek ik grafen, graafproblemen, algoritmen die deze problemen op zullen lossen, en visualizaties die zullen helpen deze oplossingen beter te kunnen begrijpen.

Mijn dank aan promotor Prof. Dr. Marc Gyssens en begeleider Bart Moelans, voor hun geduld, aanwijzingen en inspiratie, zonder welke ik dit project niet tot in de huidige staat gekregen zou hebben.


\newpage
\tableofcontents
\newpage

\chapter{Inleiding}\label{Text:Inleiding}
\section{Inleiding}\label{Text:Inleiding:Inleiding}
Veel situaties zijn te representeren door grafen. Indien men informatie over een dergelijke situatie probeert te winnen, kan dit vaak vertaald worden in een graafprobleem. De wijze waarop dit gebeurt is in de regel niet simpel te vatten. Hoe kan men er zeker van zijn wat een algoritme precies doet, of het wel daadwerkelijk de informatie helpt bemachtigen waar iemand naar op zoek is? Hoe kan men er zeker van zijn dat dit algoritme \"uberhaupt wel tot een correcte oplossing komt?

Dit thesisproject handelt rond deze problematiek. Er zal getracht worden de correctheid van een algoritme gemakkelijker te begrijpen te maken, door de werking van dit algoritme visueel weer te geven. Dit eerste hoofdstuk zal handelen rond de context waarin gewerkt zal worden. Ook zal het enkele voorbeelden bevatten waar getoond wordt hoe een visualisering behulpzaam kan zijn om een algoritme beter te begrijpen.

Dit hoofdstuk dient als een inleiding tot de problematiek waarrond dit project werkt. Hoofdstuk~\ref{Text:Doelstellingen} zal aangeven aan welke doelstellingen een programma dat ons hiermee probeert te helpen dient te voldoen. Meer specifiek zullen dit de doelstellingen zijn die aan de basis van dit thesisproject liggen. Hoofdstuk~\ref{Text:Gebruik} zal in detail uiteenzetten hoe het resulterende programma te gebruiken is. In hoofdstuk~\ref{Text:Plugin} zal dieper ingegaan worden op hoe men precies een algoritme aan dit project toe kan voegen. Een bespreking en beoordeling van het programma zullen volgen in~\ref{Text:Programma}. Haar ADTs worden besproken in~\ref{Text:ADTs} en tot slot zullen enkele visualizaties voor een paar graafproblemen getoond worden in hoofdstuk~\ref{Text:Visualizaties}.

\section{Een graaf}\label{Text:Inleiding:Graaf}
Een graaf is een verzameling van knopen en bogen (of paden), ook nodes en edges genoemd. Deze paden verbinden twee knopen, deze knopen kunnen mogelijk dezelfde zijn. Sommige grafen laten enkel toe dat een pad in \'e\'en richting `bewandeld' wordt; andere grafen laten dit in beide richtingen toe. Buiten dit is het ook mogelijk dat er knopen in een graaf bestaan die helemaal niet via een pad verbonden worden met de rest, of zelfs dat een graaf bestaat uit twee of meerdere deelgrafen die onderling niet verbonden zijn.

\begin{figure}[h!]
\centering
	\begin{tabular}{|c|c|c|}
	\hline
	\\
	\includegraphics[scale=.35]{images/graph1.png}&
	\includegraphics[scale=.3]{images/graph2.png}&
	\includegraphics[scale=.25]{images/graph3.png}
	\\
	\hline
	\end{tabular}
\caption{Verschillende grafen}
\label{Image:Graph}
\end{figure}

In figuur~\ref{Image:Graph} ziet men drie verschillende grafen die ieder op zich enigszins bijzonder zijn. Van links naar rechts is de eerste een zeer simpele, bidirectionele graaf. Dit betekent dat de paden in beide richtingen te bewandelen zijn. Alle knopen zijn hier ook onderling door paden verbonden. 

De tweede graaf is een voorbeeld van een directionele graaf; paden kunnen hier enkel in \'e\'en richting doorlopen worden. Hier valt meteen op dat we \'e\'en knoop hebben die totaal niet verbonden is met de rest van de andere knopen. Ook merken we dat het toegelaten is meerdere paden van de ene naar de andere knoop in een graaf te hebben. Tot slot merken we ook op dat de bogen hier een label dragen, die in dit geval bijvoorbeeld de kost van het bewandelen van een pad zouden kunnen beschrijven. 

Uiteindelijk bekijken we ook de derde graaf. Deze is speciaal omdat het in feite een boom is. Vanaf de bovenste knoop (gelabeld met een 1), kan er enkel verder naar beneden gelopen worden. In dit geval is ook getoond dat ook de knopen zelf een label mogen dragen, zelf al hebben de bogen dat in dit geval niet.

Om dit in het kort samen te vatten kunnen we op volgende wijze een graaf defini\"eren:

\begin{itemize}
\item Graaf:
	\begin{itemize}
		\item Is ofwel gericht ofwel ongericht.
		\item Bevat knopen:
		\begin{itemize}
			\item Een knoop kan een label dragen.
			\item Een knoop is uniek.
		\end{itemize}
		\item Bevat bogen:
		\begin{itemize}
			\item Een boog verbindt precies twee knopen.
			\item Een boog kan een label dragen.
			\item Alle bogen in een graaf kunnen ofwel in \'e\'en ofwel in beide richtingen doorlopen worden, afhankelijk van of de graaf gericht is.
			\item Een boog kan een knoop met zichzelf verbinden.
			\item Bogen zijn niet uniek. Er kunnen twee of meer bogen tussen dezelfde twee knopen zijn, eventueel zelfs met hetzelfde label.
		\end{itemize}
	\end{itemize}
\end{itemize}

Nu beschouwd is wat een graaf precies is, mag bekeken worden waar een graaf precies voor gebruikt kan worden. Een graaf is een datastructuur die zeer verscheidene situaties kan modelleren. In het meest voordehandliggende voorbeeld stelt iedere knoop een locatie voor, waar elk pad een weg tussen deze twee locaties voorstelt. Er zijn echter veel meer situaties die door een graaf gemodelleerd kunnen worden, zoals bijvoorbeeld een LAN netwerk, of een spoorwegenkaart.

Om dit voorbeeld beter zichtbaar te maken, beschouw een beperkt fragment van de kaart van de stad Hasselt in figuur~\ref{Image:Map}.

\begin{figure}[h!]
\centering
	\includegraphics[scale=0.5]{images/map.PNG}
\caption{Fragment kaart Hasselt}
\label{Image:Map}
\end{figure}

Dit valt als graaf voor te stellen bijvoorbeeld zoals men ziet in figuur~\ref{Image:MapGraph}. Ter verduidelijking zijn enkele langere straten gekleurd. Zelfs al is deze voorstelling visueel minder representatief voor de daadwerkelijke layout van dit fragment, het voordeel van deze voorstelling is dat er eventueel mee gerekend kan worden; terwijl de voorstelling van de kaart als afbeelding in figuur~\ref{Image:Map} voor een computerprogramma grotendeels onbruikbaar is.

\begin{figure}[h!]
\centering
	\includegraphics[scale=.25]{images/map_graph.png}
\caption{Fragment kaart als graaf}
\label{Image:MapGraph}
\end{figure}

\section{Graafproblemen}\label{Text:Inleiding:Graafprobleem}
In de vorige sectie werd besproken hoe men gebruik kan maken van grafen om een situatie voor te stellen. Uiteraard willen we deze datastructuur gebruiken om meer informatie over de situatie die zij voorstelt te winnen dan op het moment beschikbaar is. Het winnen van dergelijke informatie, wat zo eenvoudig kan zijn als het beantwoorden van een ja/nee-vraag ligt aan het hart van een graafprobleem.

Voor een groot deel zal er voor dergelijke vragen over informatie over een graaf een antwoord beschikbaar zijn. Dit antwoord wordt verkregen door een algoritme op deze graaf uit te voeren. Een algoritme kan bekeken worden als een soort stappenplan om deze informatie te bemachtigen.

Een voorbeeld van een zeer bekend probleem is het handelsreizigersprobleem. In dit geval wordt de graaf gebruikt om locaties voor te stellen, de knopen zijn steden, de paden zijn wegen. Het graafprobleem is dan "Is het mogelijk iedere stad slechts \'e\'enmaal te bezoeken en aan het einde van de rit toch alle steden bezocht te hebben?".

Om een voorbeeld van een algoritme te geven beschouwen we best een ander probleem; algoritmes die streven het handelsreizigersprobleem op te lossen zijn te complex om hier te bespreken. 

Gegeven een graaf, defini\"eer ons probleem als volgt: "Gegeven een willekeurige start- en eindknoop. Zijn deze knopen verbonden door een pad?". Als we de tweede graaf in figuur~\ref{Image:Graph} bekijken, zien we dat er bijvoorbeeld geen pad bestaat tussen knoop 1 en eender welke andere knoop.

De pseudo-code in listing~\ref{Alg:Path} geeft een voorbeeld van een algoritme dat dit probleem oplost.

\begin{lstlisting}[language={}, caption={PATH algoritme}, label={Alg:Path}]
Zij $l$ een lege lijst van knopen.
Noem $n_{start}$ de startknoop en $n_{eind}$ de eindknoop.
Voeg $n_{start}$ toe aan $l$.
Voor iedere knoop $k$ in $l$ doe:
	Voor iedere boog $b$ in de graaf doe:
		Als $b$ begint in $k$:
			Zij $x$ de knoop waarin $b$ aankomt.
			Als $x = n_{eind}$:
				return true.
			Als $x \not\in l$: Voeg $x$ toe in $l$.
return false.
\end{lstlisting}

In listing~\ref{Alg:Path} zien we dan inderdaad een stappenplan dat uitgevoerd kan worden met een bepaalde graaf als input, dat uiteindelijk in haar lijst $l$ alle knopen zal bevatten die vanuit de startknoop bereikbaar zijn. In het bijzonder, als we willen weten of knoop $x$ bereikbaar is, kunnen we dat aan het einde van het algoritme testen, door te kijken of deze knoop zich in de lijst $l$ bevat.

\section{Correctheid van algoritmen}\label{Text:Inleiding:Correctheid}
In listing~\ref{Alg:Path} werd een algoritme getoond waarvan beweerd werd dat het het probleem beschreven in sectie~\ref{Text:Inleiding:Graafprobleem} oplost. Echter, hoe kan men zich er van verzekeren dat deze bewering juist is, dat dit algoritme inderdaad het probleem oplost? In dit geval is een corectheidsbewijs nodig. Om tot een correctheidsbewijs te komen is eerst een goed inzicht in het algoritme zelf benodigd. Hoe komen we tot dit begrip?

Een na\"ieve methode om tot een dergelijk begrip te komen bestaat uit het grondig nalezen van het algoritme. Men zal dan door in het hoofd te visualizeren wat er gebeurt proberen na te gaan wat er precies in iedere stap gebeurt.

Een andere methode zou er uit bestaan om een graaf, of een deel ervan, uit te tekenen en op deze manier na te gaan hoe het algoritme werkt. Ook hier zijn echter nadelen aan, het uittekenen van grafen neemt veel tijd in beslag en het zou veel tijd kosten op deze manier voor meerdere situaties na te gaan dat dit algoritme inderdaad doet wat het beweert.

Men kan inzien dat het tot begrip van een algoritme komen een langdurig proces kan zijn. Voor degene die het algoritme ontworpen heeft is dit misschien niet zo, maar niet iedereen heeft uiteraard voor het ontstaan van dit algoritme met de ontwerper meegedacht. Hoe kan een leek inzien dat dit algoritme werkt? Hoe ziet een leek wat dit algoritme doet, als hij bijvoorbeeld niet de achtergrond heeft om het beschreven algoritme \"uberhaupt te lezen? Sectie~\ref{Text:Inleiding:Visualizatie} handelt rond deze problematiek.

\section{Visualizatie}\label{Text:Inleiding:Visualizatie}
In sectie~\ref{Text:Inleiding:Correctheid} werd ingeleid dat het tot begrip komen over de werking van een algoritme niet altijd een gemakkelijk proces is. Om dit proces te vergemakkelijken, ook voor zij die moeite hebben een algoritme gegeven in pseudocode te lezen, introduceren we geautomatiseerde visualizatie.

Dit houdt in, gegeven een algoritme en een graaf, dat stap voor stap getoond zal worden wat dit algoritme precies doet. Twee voorbeelden van dergelijke visualizaties zullen hieronder gegeven worden.

\subsection{Path probleem}\label{Text:Inleiding:Visualizatie:Path}
Het algoritme dat gevisualizeerd zal worden is al gepresenteerd in sectie~\ref{Text:Inleiding:Graafprobleem}. Voor het gemak van de lezer wordt dat in listing~\ref{Alg:Path2} herhaald.

\begin{lstlisting}[language={}, caption={PATH algoritme}, label={Alg:Path2}]
Zij $l$ een lege lijst van knopen.
Noem $n_{start}$ de startknoop en $n_{eind}$ de eindknoop.
Voeg $n_{start}$ toe aan $l$.
Voor iedere knoop $k$ in $l$ doe:
	Voor iedere boog $b$ in de graaf doe:
		Als $b$ begint in $k$:
			Zij $x$ de knoop waarin $b$ aankomt.
			Als $x = n_{eind}$:
				return true.
			Als $x \not\in l$: Voeg $x$ toe in $l$.
return false.
\end{lstlisting}

De graaf aan de hand van welke dit algoritme gevisualizeerd wordt, wordt getoond in figuur~\ref{AlgPath:Begin}. Als startknoop nemen we de knoop met label $2$, als eind de knoop met label $5$.

\ctable[pos=h!t, botcap, figure, caption={Startgraaf}, label={AlgPath:Begin}]{c}{}{
\includegraphics[scale=.35]{images/AlgPath/graph_screen_1.png}
}

Gegeven het algoritme en een graaf, nu kan men in figuur~\ref{AlgPath:Exec} de visualizatie van dit algoritme aanschouwen.

\ctable[pos=h!t, botcap, figure, caption={Visualisatie PATH}, label={AlgPath:Exec}]{ccc}{}{
\includegraphics[scale=.3]{images/AlgPath/graph_screen_2.png}&
\includegraphics[scale=.3]{images/AlgPath/graph_screen_3.png}&
\includegraphics[scale=.3]{images/AlgPath/graph_screen_4.png}
\\
(1) & (2) & (3)
\\
\includegraphics[scale=.3]{images/AlgPath/graph_screen_5.png}&
\includegraphics[scale=.3]{images/AlgPath/graph_screen_6.png}&
\includegraphics[scale=.3]{images/AlgPath/graph_screen_7.png}
\\
(4) & (5) & (6)
\\
\includegraphics[scale=.3]{images/AlgPath/graph_screen_8.png}&
\includegraphics[scale=.3]{images/AlgPath/graph_screen_9.png}&
\includegraphics[scale=.3]{images/AlgPath/graph_screen_10.png}
\\
(7) & (8) & (9)
\\
&
\includegraphics[scale=.3]{images/AlgPath/graph_screen_11.png}&
\\
& (10) &
}

Nu kunnen we het verloop van het algoritme op de volgende manier uitleggen.
\begin{enumerate}
\item De beginknoop wordt rood gemarkeerd. Dit is de eerste knoop die in lijst $l$ toegevoegd werd. Gezien dit de beginknoop is, is deze uiteraard bereikbaar.
\item We bekijken een willekeurige boog vanuit de beginknoop. Deze markeren we groen.
\item De eindknoop van laatst gemarkeerde boog kennen we nog niet. We markeren deze rood, het is dus bereikbaar.
\item We bekijken een volgende boog en markeren deze.
\item Ook haar eindknoop kennen we nog niet, dus markeren we deze.
\item We bekijken een volgende boog.
\item Haar eindknoop kennen we, dus wordt deze niet gemarkeerd. We bekijken een volgende boog.
\item Ook haar eindknoop kennen we. We gaan verder vanuit een nieuwe bereikbare (gemarkeerde) knoop. Vanuit deze (knoop 3), nemen we weer een willekeurige boog en markeren deze.
\item Haar eindknoop (knoop 4) kennen we weer, dus beschouwen we weer een volgende boog.
\item Knoop 5 is nog niet gemarkeerd. Deze markeren we nu. We merken op dat dit onze gekozen eindknoop was en returnen $true$.
\end{enumerate}

In deze sectie werd getoond hoe visualizatie kan helpen het path algoritme visueel weer te geven. In de volgende sectie zal een ander type probleem besproken worden.

\subsection{Minimum spanning tree}\label{Text:Inleiding:Visualizatie:Kruskal}
In deze sectie zal een ander algoritme voor een ander probleem gevisualizeerd worden. Dit is het probleem van het vinden van de `minimum spanning tree' (minimale omspannende boom). Dit probleem kan gedefini\"eerd worden als volgt: "Gegeven een gewogen graaf\footnote{Gewogen graaf: Een graaf waarvan alle bogen een gewicht hebben.}, verwijder zoveel mogelijk paden uit deze graaf als mogelijk, terwijl de knopen zelf allen onderling verbonden blijven. De som van alle gewichten van de bogen moet in dit resultaat minimaal zijn".

Een algoritme dat dit probleem op kan lossen is het algoritme van Kruskal\cite[p.~231]{cursus}. Dit algoritme kan beschreven worden zoals in listing~\ref{Alg:Kruskal}.

\begin{lstlisting}[language={}, label={Alg:Kruskal}, caption={Kruskals algoritme}]
Maak een verzameling van bomen $F$, zodat elke knoop van de graaf in %\'e\'en) aparte boom zit.
Maak een verzameling $S$ van alle bogen van de graaf.
Zolang $S$ niet leeg is, doe:
	Verwijder een boog met minimum gewicht uit $S$. Noem deze boog $B$.
	Als $B$ twee verschillende bomen verbindt: 
		Verwijder de twee bomen $b_1$ en $b_2$ uit $F$.
		Verdind $b_1$ en $b_2$ door $B$. Noem het resultaat $b'$.
		Voeg $b'$ toe aan $F$.
$F$ bevat nu slechts %\'e\'en) element, de minimum omspannende boom voor gegeven graaf.
\end{lstlisting}

Zoals bij het algoritme in sectie~\ref{Text:Inleiding:Visualizatie:Path}, is het weer enigszins ongemakkelijk in te zien hoe dit algoritme in de praktijk werkt. Stel nu dat we dit uitvoeren op de graaf in figuur~\ref{AlgKruskal:Begin}, dan zal het algoritme precies zo te werk gaan als getoond in figuur~\ref{AlgKruskal:Exec}.

\ctable[pos=h!t, botcap, figure, caption={Startgraaf}, label={AlgKruskal:Begin}]{c}{}{
\includegraphics[scale=.35]{images/AlgKruskal/graph_screen_1.png}
}

\ctable[pos=h!t, botcap, figure, caption={Uitvoering Kruskals algoritme}, label={AlgKruskal:Exec}]{cccc}{}{
\includegraphics[scale=.35]{images/AlgKruskal/kruskal1.png}&
\includegraphics[scale=.35]{images/AlgKruskal/kruskal2.png}&
\includegraphics[scale=.35]{images/AlgKruskal/kruskal3.png}&
\includegraphics[scale=.35]{images/AlgKruskal/kruskal4.png}
\\
(1)&(2)&(3)&(4)
\\
\includegraphics[scale=.35]{images/AlgKruskal/kruskal5.png}&
\includegraphics[scale=.35]{images/AlgKruskal/kruskal6.png}&
\includegraphics[scale=.35]{images/AlgKruskal/kruskal7.png}&
\\
(5)&(6)&(7)&
}

De werking van het algoritme van Kruskal zoals getoond in figuur~\ref{AlgKruskal:Exec}, uitgevoerd op de graaf getoond in figuur~\ref{AlgKruskal:Begin}, kan dan toegelicht worden als volgt.
\begin{enumerate}
\item Als boog met het laagste gewicht kiezen we $A\rightarrow D$. Merk op dat dit een willekeurige keuze is, $C\rightarrow E$ heeft namelijk dezelfde kost. We verbinden deze `bomen' met elkaar en markeren ze in de kleur van $A$.
\item Zoals eerder vermeld kiezen we nu $C\rightarrow E$. Weer markeren we deze, nu in de kleur van $C$.
\item De volgende laagste kost om twee verschillende bomen te verbinden is 6, we kiezen dus $D\rightarrow F$ en markeren deze.
\item Willekeurig voor kost 7 kiezen we $A\rightarrow B$.
\item Voor dezelfde kost kunnen we nu $B\rightarrow E$ markeren, merk op dat beide deelbomen (geel en groen) nu verbonden (groen) zijn.
\item De volgende laagste kost zou 8 zijn, voor $E\rightarrow F$. Merk op dat beide knopen $E$ en $F$ al onderling vorbonden zijn, dus in dezelfde boom zitten. We kiezen nu $E\rightarrow G$ voor kost 9.
\item Alle knopen zitten nu in \'e\'en en dezelfde boom. Dit wordt het duidelijkst getoond door alle paden van de graaf die we niet gebruikt hebben, te verwijderen. In deze deelfiguur ziet men het resultaat.
\end{enumerate}

\subsection{Conclusie}\label{Text:Inleiding:Visualizatie:Conclusie}
In sectie~\ref{Text:Inleiding:Visualizatie:Path} en~\ref{Text:Inleiding:Visualizatie:Kruskal} werden twee graafproblemen beschreven. Voor beide problemen werd een algoritme beschreven dat dit probleem op beweert te lossen. Beide algoritmen werden beschreven op een manier die volstaat om het algoritme uit te voeren, maar op zich niet gemakkelijk te begrijpen is. Na deze beschrijving werd de uitvoering van het algoritme op een voorbeeldgraaf gevisualizeerd. Opgemerkt mag worden dat, dankzij deze visualizatie, het gemakkelijker is in te zien wat deze algoritmen precies doen.

Om dit te kunnen automatiseren werd een programma voorzien. In hoofdstuk~\ref{Text:Doelstellingen} zal beschreven worden welke doelstellingen grotendeels van belang waren bij de implementatie van dit programma. Het gebruik hiervan zal beschreven worden in hoofdstukken~\ref{Text:Gebruik} en~\ref{Text:Plugin}.

\chapter{Doelstellingen}\label{Text:Doelstellingen}
In het vorige hoofdstuk is een uitleg gegeven over het nut van het visualizeren van het verloop van een algoritme. Dit kan zeer behulpzaam zijn indien men het verloop van een algoritme beter wenst te begrijpen dan men doet door enkel haar (pseudo-) code te zien. Het visualizeren van een algoritme wensen we dus te automatiseren door een programma, dat liefst geschikt is voor zo veel mogelijk verschillende graafalgoritmes.

Nu is het doel van dit hoofdstuk enkele doelstellingen te genereren waar een dergelijke automatisatie aan zou moeten voldoen.

\begin{enumerate}
\item Elk mogelijk type graaf voorstellen.
\item Een zo bruikbaar, maar nog steeds algemeen mogelijke interface bieden voor het werken met grafen.
\item Wijzigingen in de structuur van de graaf kunnen weergeven. (Zie de laatste afbeeldingen in figuur~\ref{AlgKruskal:Exec}, dergelijke wijzigingen willen we kunnen zien).

Nu is de vraag, wat hebben zoveel mogelijk graafalgoritmes gemeen met elkaar, op zo'n manier dat het in de doelstellingen opgenomen kan worden; de vorige drie punten zijn uiteraard nog slechts erg mager. Als we de algoritmen in listing~\ref{Alg:Path} en listing~\ref{Alg:Kruskal} met elkaar vergelijken kunnen we opmerken dat de voortgang van het algoritme in beide gevallen in een soort van lijst type bijgehouden wordt. Vandaar de vierde doelstelling:
\item Een zo algemeen mogelijk lijst-type aanbieden dat de gebruiker kan benutten om informatie in op te slaan. Dit zal gebruikt moeten kunnen worden om bijvoorbeeld knopen, bogen, getallen, etc op te kunnen slaan. Het programma zal het gebruik hiervan kunnen benutten om informatie over het algoritme te winnen.

Tussen deze algoritmen zijn verder geen grote algemeenheden meer te vinden. Echter, om toch nog iets meer bruikbaarheid aan te kunnen bieden maken we een vijfde doelstelling:
\item Aan de gebruiker toelaten tijdens de voortgang van het algoritme een specifieke knoop of boog manueel te markeren om op deze manier informatie over het algoritme te communiceren. Indien de eerste vier doelstellingen niet genoeg zijn om het verloop van een algoritme degelijk te tonen, kan op z'n minst de gebruiker hier zelf nog enigszins aan sleutelen.
\item Bijhouden hoeveel de gebruikte structuren gequeried worden, zodat de gebruiker een beeld krijgt van de complexiteit van het algoritme.
\item Aan de gebruiker toelaten tijdens de uitvoering van zijn zelfgeschreven algoritme commentaar te geven op de gevolgde stappen en dit weer te geven.
\end{enumerate}

\chapter{Gebruik}\label{Text:Gebruik}
Dit deel van dit verslag zal handelen rond hoe dit project gebruikt dient te worden. Eerst zal er uitgelegd worden hoe het gecompileerd kan worden. Vervolgens wordt het gebruik van dit project voor de visualisatie van een daadwerkelijk algoritme uitgelegd. Dit gedeelte zal voldoende ge\"illustreerd worden aan de hand van voorbeelden.

\section{Installatie van het project}\label{Text:Gebruik:Installatie}
Dit thesisproject is afhankelijk van enkele libraries. Deze zijn QtGui en QtCore\cite{qt:download}. Een afhankelijk die minder duidelijk is is het GraphViz\cite{graphviz:download} project, van welke de DOT\cite{graphviz:dot} tool gebruikt wordt om een Graaf te kunnen tonen. Het dot commando behoort in het path beschikbaar te zijn.

\subsection{Installatie onder linux}\label{Text:Gebruik:Installatie:Linux}
Voor linuxgebruikers is er bij dit project een compile script toegevoegd: \emph{compile.sh}. Deze zal eerst het project als library compileren en installeren. Hiervoor kunnen administratorrechten gevraagd zijn. Zodra dit voltooid is wordt de applicatie op zich gecompileerd. Tot slot worden alle plugins in de plugin map ook gecompileerd.

De locatie waar dit project ge\"installeerd wordt is standaard `/usr/local/lib/' en `/usr/local/include/graafalgoritmes/'. Dit kan gewijzigd worden in \emph{graafalgoritmes\_lib.pro}, maar in alle andere .pro files moet dan wel het includepath aangepast worden.

\subsection{Installatie onder windows}\label{Text:Gebruik:Installatie:Windows}
Ook voor windowsgebruikers is er een compile script toegevoegd\footnote{In het bijgeleverde script wordt een standaard-installatie verondersteld. Het dient aangepast te worden indien dit niet het geval is.}. Dit is \emph{compile.bat}. Dit handelt geheel analoog aan het linux equivalent. De gebruiker zal echter wel waarschijnlijk het installatiepad willen aanpassen. Standaard zou dit terecht komen in `C:/usr/local/'.

De installatie dient uitgevoerd te worden in de opdrachtprompt (\emph{cmd.exe}). Tijdens de installatie moet men zich ervan verzekeren dat de Qt libraries zich in het path bevinden. Bij een standaard Qt installatie wordt dit niet gedaan. Best kan dit dus in de door Qt bijgeleverde `Qt Command Prompt' gedaan worden. In dit geval moet men wel manueel de locatie van de DOT tool aangeven voor de uitvoering van het programma op zich. Dit kan gedaan worden door een ander script \emph{adjustPathForWindows.bat} aan te roepen. Dit zal het path uitbreiden met de standaardlocatie van de DOT tool en het bestand \emph{graafalgoritmes\_app.exe} in de map \emph{debug} uitvoeren.


\section{Opbouwen van een graaf}\label{Text:Gebruik:Opbouw}
Er zijn twee mogelijkheden voorzien om een graaf uit een file te laden. Een eerste is een simpel tekstformaat, een tweede is via xml. Beide manieren zullen in de volgende twee secties besproken worden.

\subsection{Inladen van tekst}\label{Text:Gebruik:Opbouw:Custom}
De syntax van de file vanwaar een graaf ingeladen zou moeten worden is heel simpel. In de file is commentaar toegelaten door een hele regel achter \function{//} te zetten. Lege regels zijn alsook toegelaten. Als een van de eerste regels zal een gebruiker \function{directed=true} ofwel \function{directed=false} willen gebruiken om aan te geven of het hier om een gerichte ofwel een ongerichte graaf gaat. Dit mag echter eender waar in de file gebeuren. De laatst gevonden waarde wordt gebruikt en indien niet gevonden wordt een ongerichte graaf aangemaakt.

Op dit punt kunnen we knopen en paden toe gaan voegen. Een knoop wordt toegevoegd door een statement als \function{Node( int id )} of \function{Node( int id, string label )} toe te voegen. In dit geval is de gebruiker er volledig voor verantwoordelijk om aan iedere knoop een unieke identifier te geven. Deze identifier zal later nodig zijn om paden toe te voegen. Een label is uiteraard optioneel.

Om een pad toe te voegen kan een statement \function{Edge( int nodeFrom, int nodeTo, string label )} of \function{Edge( int nodeFrom, int nodeTo )} toegevoegd worden. De eerste twee parameters zijn de identifiers behorende bij de eerder toegevoegde knopen. De laatste parameter, het label, is volledig optioneel.

Dit is alles wat benodigd is om een volledige graaf in te kunnen laden. Een vlug voorbeeld van hoe dit er dan precies uit zal zien wordt gegeven in appendix~\ref{Appendix:File}.

\subsection{Inladen van xml}\label{Text:Gebruik:Opbouw:XML}
De syntax van een xml file is eveneens zeer gemakkelijk. Als root element wordt de \function{graph} gebruikt. Eventueel kan als attribuut \function{directed} met als waarde \function{true} of \function{false} meegegeven worden.

Binnen dit root element kunnen knopen en bogen toegevoegd worden. Een knoop element heet \function{node} en kan als attributen \function{label} met een string waarde en \function{identifier} met een integer waarde hebben. Indien geen \function{identifier} attrituut gespecifi\"eerd wordt, wordt een identifier gegenereerd, beginnend van 0.

Een boog element wordt \function{edge} genoemd en heeft vier mogelijke attributen. Ten eerste de verplichte attributen \function{from} en \function{to}, die een integerwaarde krijgen. Deze behoren geldige identifiers voor knopen te zijn. Ook voor een boog is het mogelijk een \function{label} attribuut te specifi\"eren. Tot slot kan ook hier een \function{identifier} toegekend worden, maar dit is optioneel.

Een voorbeeld van hoe een graaf in xml gespecifi\"eerd kan worden wordt getoond in appendix~\ref{Appendix:Xml}.

\section{Gebruik van het programma}
Het gebruik van het programma zelf zal met enkele screenshots toegelicht worden. Indien men het programma opstart, ziet men het scherm in figuur~\ref{App:Interface1}.

\ctable[pos=h!t, figure, botcap, caption={Interface}, label={App:Interface1}]{c}{}{\includegraphics[scale=.5]{images/interface/interface1.png}}

Om iets te hebben om te visualizeren dient een algoritme geselecteerd te worden. Hiervoor klikt men op het `Algorithm' menu en ziet men een lijst van algoritmen die als plugin gedetecteerd zijn. Zodra een algoritme gekozen is (hier: Prim's Algoritme) ziet men het scherm in figuur~\ref{App:Interface2}. Meer informatie over hoe een plugin gecre\"eerd kan worden vindt men in hoofdstuk~\ref{Text:Plugin}.

\ctable[pos=h!t, figure, botcap, caption={Interface}, label={App:Interface2}]{c}{}{\includegraphics[scale=.5]{images/interface/interface2.png}}

Nu hebben we een algoritme gekozen, maar nog geen graaf om dit om uit te voeren. Om een graaf te selecteren klikt men op `Graph', dan `Choose...', en selecteert men het bestand waarin de gewenste graaf gedefini\"eerd is. De geselecteerde graaf wordt getoond en u wordt om bevestiging gevraagd. Na de bevestiging krijgt het algoritme de kans deze graaf te weigeren. Indien u accepteert, zal u het scherm in figuur~\ref{App:Interface3} te zien krijgen.

\ctable[pos=h!t, figure, botcap, caption={Interface}, label={App:Interface3}]{c}{}{\includegraphics[scale=.5]{images/interface/interface3.png}}

%temp
\newpage
Nu is alle benodigde informatie klaar om een visualizatie van het gekozen algoritme op de gekozen graaf te starten. Men klikt op `Show', en het scherm zoals in figuur~\ref{App:Interface4} zal verschijnen.

\ctable[pos=h!t, figure, botcap, caption={Interface}, label={App:Interface4}]{c}{}{\includegraphics[scale=.35]{images/interface/interface4.png}}

Nu kan men ofwel door play en stop, ofwel door step, stap voor stap de uitvoering van het algoritme bekijken. Een voorbeeld van wat u tegen zal komen in het geval van het Algoritme van Prim op de eerder getoonde graaf wordt getoond in figuur~\ref{App:Interface5}.

\ctable[pos=h!t, figure, botcap, caption={Interface}, label={App:Interface5}]{c}{}{\includegraphics[scale=.35]{images/interface/interface5.png}}

In figuur~\ref{App:Interface5} merkt men ten eerste de markeringen op de graaf op. Bij het algoritme van Prim stellen deze de edges en nodes voor die in de minimum spanning tree opgenomen worden. Duidelijk zijn er nog nodes niet gemarkeerd, dit algoritme is nog niet voltooid.

%temp
\newpage
Aan de rechteronderkant ziet men `Container 0'. Hier wordt de inhoud van de gebruikte container gezien. Grofweg stelt dit de voortgang van het algoritme voor. Deze container zal uiteindelijk de gehele minimum spanning tree bevatten. Ook kan men aan de rechterbovenkant `Graph Access' herkennen. Hier wordt bijgehouden hoeveel queries er precies op de graaf uitgevoerd worden. Tot slot ziet men een leeg wit vlak. In dit gebied kan de auteur van een algoritme commentaar geven op het verloop. Hier kunnen bijvoorbeeld resultaten weergegeven worden, of eender welke andere tussentijdse informatie.

\chapter{Implementatie van een plugin}\label{Text:Plugin}
In dit hoofdstuk zal in detail besproken worden hoe men een plugin voor dit programma kan schrijven. Er zal vertrokken worden van enkel de pseudo-code voor een algoritme en dit zal stap voor stap verfijnd worden tot een daadwerkelijke plugin.

Informatie over de ADTs die hier gebruikt worden, die een gebruiker dus zelf nodig heeft indien hij een plugin zou schrijven, kan gevonden worden in hoofdstuk~\ref{Text:ADTs}. De twee meest relevante modules, \class{Graph} en \class{Algorithm}, worden besproken in respectievelijk sectie~\ref{Text:ADTs:Graph} en sectie~\ref{Text:ADTs:Algorithm}.

\section{Voorbereiding}\label{Text:Plugin:Voorbereiding}

Het algoritme dat gekozen is om te dienen als voorbeeld voor dit hoofdstuk is het reverse-delete algoritme\cite{reversedelete}. Dit algoritme kan zoals in listing~\ref{Alg:Reversedelete} weergegeven worden. Dit algoritme vindt de minimum spanning tree van een graaf, zoals beschreven in sectie~\ref{Text:Inleiding:Visualizatie:Kruskal}. Indien deze graaf meerdere deelgrafen bevat zal het voor iedere deelgraaf de MST berekenen.

\begin{lstlisting}[caption={Reverse-delete algoritme}, label={Alg:Reversedelete}, language={}]
Gegeven een lijst van edges $E$.
Sorteer $E$ op het gewicht van de edges van hoog naar laag.
Voor alle edges $e\in E$ doe:
	Als er een pad bestaat, zonder $e$, dat $e.from$ met $e.to$ verdindt:
		Verwijder $e$ uit $E$.
$E$ bevat nu de MST.
\end{lstlisting}

Als eerste stap, met de datastructuren die voor ons beschikbaar zijn, kunnen we dit als in listing~\ref{Alg:Reversedelete2} vertalen. We kunnen niet zomaar starten met een lijst van edges, maar moeten deze eerst uit de graaf lezen. Tot slot kunnen we de edges die verwijderd worden ook gewoon uit de graaf verwijderen, gezien dit visueel het meest aantrekkelijk zal zijn.

\begin{lstlisting}[caption={Reverse-delete algoritme}, label={Alg:Reversedelete2}, language={}]
Gegeven een graaf $G$.
%Defini\"eer) $E$ een lijst van edges.
Voor alle edges $e\in G$ doe:
	Voeg $e$ toe aan $E$.
Sorteer $E$ op het gewicht van de edges.
Voor alle edges $e\in E$ doe:
	Verwijder $e$ uit $E$.
	Als er een pad bestaat, zonder $e$, dat $e.from$ met $e.to$ verbindt:
		Verwijder $e$ uit $G$.
$G$ bevat nu haar MST.
\end{lstlisting}

Als tweede stap kunnen we het gebruik van een Container introduceren en deze pseudocode vertalen tot het resultaat in listing~\ref{Alg:Reversedelete3}.

\begin{lstlisting}[caption={Reverse-delete algoritme}, label={Alg:Reversedelete3}, language={}]
Gegeven een graaf $G$.
%Defini\"eer) $E$ een lijst van edges.
%Defini\"eer) een container $c$.
Voor alle edges $e\in G$ doe:
	Voeg $e$ toe aan $E$.
Tot $E$ leeg is, doe:
	Verwijder de edge met hoogste kost uit $E$ en voeg dit van achteren toe aan $c$.
Tot $c$ leeg is, doe:
	Neem $e$ de voorste edge uit $c$ en verwijder deze.
	Als $G$ een pad tussen $e.from$ en $e.to$ bevat zonder $e$, doe:
		Verwijder $e$ uit $G$.
$G$ bevat nu haar MST.
\end{lstlisting}

\section{Implementatie}\label{Text:Plugin:Implementatie}

De pseudocode in listing~\ref{Alg:Reversedelete3} is nu klaar om in C++ omgezet te worden. Eerst beschouwen we een header file in listing~\ref{Alg:Reversedelete4}

\begin{lstlisting}[caption={AlgReverseDelete.h}, label={Alg:Reversedelete4}]
#ifndef ALGREVERSEDELETE_H
#define ALGREVERSEDELETE_H

//De nodige includes.
#include<QList>
#include<Algorithm.h>
#include<ContainerElement.h>

//De klasse waarin we werken, afgeleid van Algorithm.
class AlgReverseDelete: public Algorithm{
public:
	//Constructor en destructor.
	AlgReverseDelete( Graph *g );
	~AlgReverseDelete();
	
	//Hier wordt ons algoritme uitgevoerd.
	virtual void run();
private:
	//Deze functie gebruiken we om niet steeds container(0) te moeten callen. Dit veronderstelt dat er al een container toegevoegd is.
	Container &c(){ return container(0); }
	//Deze functie geeft terug of $G$ een pad tussen $e.from()$ en $e.to()$ bevat zonder $e$.
	bool existsOtherPath( const Edge &e );
};

#endif
\end{lstlisting}

Constructor en destructor worden getoond in listing~\ref{Alg:Reversedelete5}.

\begin{lstlisting}[caption={AlgReverseDelete.cpp: constructor en destructor}, label={Alg:Reversedelete5}]
#include"AlgReverseDelete.h"

AlgReverseDelete::AlgReverseDelete( Graph *g ):Algorithm(g){
	//De functie Container &c(); veronderstelt dat we al een Container hebben. Deze voegen we hier toe.
	containerAdd();
}

AlgReverseDelete::~AlgReverseDelete(){

}
\end{lstlisting}

De code in listing~\ref{Alg:Reversedelete5} zou niet verassend moeten zijn. Er wordt \'e\'en Container klaargemaakt en dat is alles. Gezien deze klasse geen membervariabelen heeft is het niet nodig iets te deleten. Volgende code in listing~\ref{Alg:Reversedelete7} is de implementatie van $bool$ $existsOtherPath( const Edge \&e );$. De code in listing~\ref{Alg:Reversedelete6} geeft hier eerst de pseudocode voor.

\begin{lstlisting}[caption={pseudocode existsOtherPath}, label={Alg:Reversedelete6}, language={}]
Neem $reachableNodes$ een lijst van alle bereikbare knopen.
Voeg $e.from()$ toe aan $reachableNodes$.
Voor alle nodes $currentNode$ in $reachableNodes$, doe:
	Voor alle edges $currentEdge$ in $G$ doe:
		Als $currentEdge\not = e$ en $currentEdge$ ofwel start of eindigt in $currentNode$:
			Als de andere node van $currentEdge$ gelijk is aan $e.to()$
				return true.
			anders
				voeg deze node toe aan $reachableNodes$.
return false.
\end{lstlisting}

\begin{lstlisting}[caption={AlgReverseDelete.cpp: existsOtherPath}, label={Alg:Reversedelete7}]
//Deze functie kijkt na of $G/e$ een pad tussen $e.from()$ en $e.to()$ bevat. Dit is grotendeels gelijk aan het algoritme in sectie%~\ref{Text:Inleiding:Visualizatie:Path}).
bool AlgReverseDelete::existsOtherPath( const Edge &e ){
	//Deze lijst zal alle nodes bevatten die we bereiken kunnen vanuit $e.from()$.
	QList<Node> reachableNodes;
	reachableNodes.push_back(e.from());
	
	//Voor alle bereikbare nodes...
	for( int i = 0; i < reachableNodes.size(); i++ ){
		//Sla deze node tijdelijk op voor makkelijker gebruik.
		const Node currentNode = reachableNodes[i];
		
		//Voor alle edges in the graaf...
		for( int j = 0; j < graph()->numEdges(); j++ ){
			//Sla deze edge tijdelijk op voor makkelijker gebruik
			const Edge &currentEdge = graph()->edge(j);
			
			//Als deze edge gelijk is aan $e$ doen we alsof ze niet bestaat.
			if( currentEdge == e )
				continue;
			
			//Als deze edge begint vanuit $currentNode$
			if( currentEdge.from() == currentNode ){
			
				//Als ze uitkomt in "e.to()" bestaat er dus inderdaad een pad.
				if( currentEdge.to() == e.to() )
					return true;
				
				//Kijk na of deze knoop al toegevoegd is, en voeg haar toe als dit niet het geval is.
				bool alreadyContained = false;
				for( int k = 0; k < reachableNodes.size() && !alreadyContained; k++ )
					alreadyContained = currentEdge.to() == reachableNodes[k];
				if(!alreadyContained)
					reachableNodes.push_back(currentEdge.to());
			
			//Gezien we enkel met ongerichte grafen werken, moeten we ook $currentEdge.to()$ beschouwen.
			}else if( currentEdge.to() == currentNode ){
				if( currentEdge.from() == e.to() )
					return true;
				bool alreadyContained = false;
				for( int k = 0; k < reachableNodes.size() && !alreadyContained; k++ )
					alreadyContained = currentEdge.from() == reachableNodes[k];
				if(!alreadyContained)
					reachableNodes.push_back(currentEdge.from());
			}
		}
	}
	//Als op geen moment een knoop gelijk aan $e.to()$ gevonden is, bestaat er dus geen pad.
	return false;
}
\end{lstlisting}

Tot slot ontbreekt nog de implementatie van \function{run()}. Deze zal in fragmenten getoond worden om het lezen te vergemakkelijken. De pseudocode in~\ref{Alg:Reversedelete3} zal als commentaar herhaald worden. De betreffende fragmenten zijn listings~\ref{Alg:Reversedelete8},~\ref{Alg:Reversedelete9}~en~\ref{Alg:Reversedelete10}.

% Gegeven een graaf $G$.
% %Defini\"eer) $E$ een lijst van edges.
% %Defini\"eer) een container $c$.
% Voor alle edges $e\in G$ doe:
% 	Voeg $e$ toe aan $E$.
% Tot $E$ leeg is, doe:
% 	Verwijder de edge met hoogste kost uit $E$ en voeg dit van achteren toe aan $c$.
% Tot $c$ leeg is, doe:
% 	Neem $e$ de voorste edge uit $c$ en verwijder deze.
% 	Als $G$ een pad tussen $e.from$ en $e.to$ bevat zonder $e$, doe:
% 		Verwijder $e$ uit $G$.
% $G$ bevat nu haar MST.

\begin{lstlisting}[caption={AlgReverseDelete.cpp: run()}, label={Alg:Reversedelete8}]
//De run functie die ons algoritme implementeert
void AlgReverseDelete::run(){
	QList<int> weights;
	QList<Edge> edges;
	
	//Voor alle edges $e\in G$ doe:
		//Voeg $e$ toe aan $edges$.
	//Buiten dit slaan we voor alle edges ook de gewichten op in een aparte QList, dit zal het sorteren vergemakkelijken.
	for( unsigned int i = 0; i < graph()->numEdges(); i++ ){
		const Edge &e = graph()->edge(i);
		edges.push_back(e);
		weights.push_back(e.label().toInt());
	}

\end{lstlisting}

Listing~\ref{Alg:Reversedelete8} toont ons een eerste deel van de initialisatie voor dit algoritme. We bereiden de lijst $E$ voor, hier $edges$ genoemd, en slaan de gewichten apart op in een lijst $weights$, puur voor het gemak tijdens het sorteren. Aan het einde van deze code zijn alle edges van $G$ opgeslagen in $edges$, alle gewichten in $weights$ zodat $\forall i: weight(edges[i]) == weights[i]$.

\begin{lstlisting}[caption={AlgReverseDelete.cpp: run()}, label={Alg:Reversedelete9}]
	comment("Start sorting edges.");
	
	//Tot $edges$ leeg is, doe:
		//Verwijder de edge met hoogste gewicht uit $edges$ en voeg dit van achteren toe aan $c$.
	while( edges.size() > 0 ){
	
		//Vind de edge met hoogste gewicht
		int max = weights[0];
		int pos = 0;
		for( int i = 1; i < edges.size(); i++ ){
			if( weights[i] > max ){
				max = weights[i];
				pos = i;
			}
		}
		
		//Verwijder deze edge en voeg ze van achteren toe aan $c$.
		c().push_back( (new ContainerElement)->setEdge(edges.takeAt(pos)) );
		weights.removeAt(pos);
	}
	comment("Edges are sorted by weight in Container 0.");
\end{lstlisting}

Listing~\ref{Alg:Reversedelete9} toont ons het einde van de initialisatie. De lijst $edges$ wordt gesorteerd in \class{Container} $c$ met behulp van de lijst $weights$. Deze code zou niet zeer verassend moeten zijn. Tot de lijst $edges$ leeg is, blijven we steeds de \class{Edge} met hoogste gewicht zoeken en deze achteraan $c$ toevoegen. Aan het einde van deze code geldt duidelijk $\forall e \in G \Rightarrow e \in c$ en $\forall 0<=i,j<c.size(): i<=j\Rightarrow weight( c[i] ) <= weight( c[j] )$.

\begin{lstlisting}[caption={AlgReverseDelete.cpp: run()}, label={Alg:Reversedelete10}]
	//Tot $c$ leeg is, doe:
		//Neem $e$ de voorste edge uit $c$ en verwijder deze.
		/Als $G$ een pad tussen $e.from$ en $e.to$ bevat zonder $e$, doe:
			//Verwijder $e$ uit $G$.
	
	//Tot $c$ leeg is, doe
	while( c().size() > 0 ){
		/Als $G$ een pad tussen $e.from$ en $e.to$ bevat zonder $e$
		if( existsOtherPath(*c()[0]->edge()) ){
		
			comment( c()[0]->edge()->toString().append(" was removed. Another path between its nodes exists.") );
			
			//Verwijder $e$ uit $G$.
			graph()->removeEdge(*c()[0]->edge());
			delete c().takeAt(0);
		}else{
			comment( c()[0]->edge()->toString().append(" is the only path between its nodes and thus is not removed.") );
			delete c().takeAt(0);
		}
	}
	comment("The MST is all that remains now.");
}
\end{lstlisting}

Ook de code in listing~\ref{Alg:Reversedelete10} zou niet moeten verbazen. Het verschil met de pseudocode is dat het verwijderen van de voorste \class{Edge} uit $c$ een beetje uitgestelt wordt. Tot $c$ leeg is, blijven we steeds de voorste \class{Edge} $e$ beschouwen. Indien $G$ een pad bevat van $e.from()$ naar $e.to()$, zonder $e$ te gebruiken, is $e$ dus niet noodzakelijk om de graaf verbonden te houden en wordt deze uit $G$ verwijderd. Tot slot verwijderen we $e$ ook nog uit $c$.

\section{Afwerking}\label{Text:Plugin:Afwerking}

Op dit moment is het volledige algoritme ge\"implementeerd. We kunnen dit echter nog niet direct compileren als een plugin; een detail ontbreekt nog. Om van dit algoritme een plugin te maken hebben we nog een klasse nodig die afgeleid wordt van \class{AlgorithmInterface} en dient als een soort factory voor dit algoritme. Gezien de code benodigd voor het maken van een plugin voor iedere plugin grotendeels hetzelfde is, wordt die hieronder gewoon gegeven. Er is geen nood aan pseudo-code.

\begin{lstlisting}[caption={AlgReverseDeletePlugin.h}, label={Alg:Reversedelete11}]
#ifndef ALGREVERSEDELETEPLUGIN_H
#define ALGREVERSEDELETEPLUGIN_H

#include<AlgorithmInterface.h>
#include<Algorithm.h>
#include"AlgReverseDelete.h"
#include<QObject>

class AlgReverseDeletePlugin: public QObject, AlgorithmInterface{
Q_OBJECT
Q_INTERFACES(AlgorithmInterface)
public:
	virtual Algorithm *createAlgorithm( Graph *g );
	virtual QString name()const{ return "Reverse-Delete Algoritme"; }
	virtual bool canAcceptGraph( Graph *g );
private:

};

#endif
\end{lstlisting}

Over listing~\ref{Alg:Reversedelete11} valt zeer weinig te zeggen, dit is echt voor alle plugins grotendeels hetzelfde, met het grootste verschil in de header file de naam van het algoritme.

\begin{lstlisting}[caption={AlgReverseDeletePlugin.cpp}, label={Alg:Reversedelete12}]
#include"AlgReverseDeletePlugin.h" 
#include<stdio.h>

Algorithm *AlgReverseDeletePlugin::createAlgorithm( Graph *g ){
	return new AlgReverseDelete(g);
}

bool AlgReverseDeletePlugin::canAcceptGraph( Graph *g ){
	bool ok = true;
	for( int i = 0; i < g->numEdges() && ok; i++ ){
		g->edge(i).label().toInt(&ok);
	}
	return ok && !g->isDirected();
}

#include<QtGui>
Q_EXPORT_PLUGIN2(algreversedeleteplugin, AlgReverseDeletePlugin) 
\end{lstlisting}

Ook de code in listing~\ref{Alg:Reversedelete12} verschilt niet veel van de standaardcode voor een plugin. Belangrijk is echter wel de implementatie van \function{bool canAcceptGraph( Graph *g )}. Op dit punt wordt ons toegelaten tests op de \class{Graph} uit te voeren en te bepalen of deze graaf wel of niet bruikbaar is voor ons algoritme. Voor het reverse-delete algoritme willen we een ongerichte graaf, waarvan elke \class{Edge} voorzien is van een label dat door de QString library omgezet kan worden naar een integer waarde. Het is dan ook precies deze tests die in haar implementatie uitgevoerd worden.

Tot slot zijn enkel nog compiler instructies benodigd om onze code tot een plugin te compileren. Gezien Qt gebruikt wordt doorheen dit project, gebruiken we dus een Qt project file om aan te geven wat er precies gecompileerd moet worden. Haar code wordt getoond in listing~\ref{Alg:Reversedelete13}.

\begin{lstlisting}[caption={AlgReverseDeletePlugin.pro}, label={Alg:Reversedelete13}, language={}]
TEMPLATE = lib
TARGET = algreversedeleteplugin
DEPENDPATH += . 
INCLUDEPATH += .
CONFIG += plugin

INCLUDEPATH += . /usr/local/include/graafalgoritmes/
LIBS += -lgraafalgoritmes

# Input
HEADERS += AlgReverseDeletePlugin.h AlgReverseDelete.h
SOURCES += AlgReverseDeletePlugin.cpp AlgReverseDelete.cpp
\end{lstlisting}

De code in listing~\ref{Alg:Reversedelete13} is voldoende indien het project op de normale wijze ge\"installeerd is. Echter, indien de headers of de library zich op een andere locatie bevindt, zal het includepath gewijzigd moeten worden.

Nu voert men simpelweg \function{qmake AlgReverseDeletePlugin.pro} uit, dan \function{make} en het resultaat zal een werkende plugin zijn die het reverse-delete algoritme voor ons visualizeert.

Een alternatieve mogelijkheid op linux is simpelweg \function{compile.sh} uit te voeren. Onder windows kan men ofwel de project file openen in Qt Creator en het op deze wijze compileren, ofwel de file \function{compile.bat} aanroepen. Meer informatie hierover is beschikbaar in secties~\ref{Text:Gebruik:Installatie:Linux} en~\ref{Text:Gebruik:Installatie:Windows}.

%TEMP
\newpage
\section{Resultaat}\label{Text:Plugin:Resultaat}
Nu we een volledig nieuwe plugin ge\"implementeerd hebben is het tijd om te kijken naar een mogelijke resulterende visualizatie. De graaf die we aan dit algoritme als input zullen geven wordt getoond in figuur~\ref{AlgReverseDelete:Begin}.


\ctable[pos=h!t, botcap, figure, caption={Startgraaf}, label={AlgReverseDelete:Begin}]{c}{}{
\includegraphics[scale=.35]{images/AlgReverseDelete/AlgReverseDelete1.png}
}

In figuur~\ref{AlgReverseDelete:Progress1} ziet men de status van het programma direct na de initialisatiestap, waar $c$ gevuld is met alle \class{Edge}s van $G$. Men kan opmerken dat er op dit moment inderdaad slechts 11 \class{Edge}-queries op de \class{Graph} uitgevoerd zijn.

\ctable[pos=h!t, botcap, figure, caption={Reverse-delete algoritme}, label={AlgReverseDelete:Progress1}]{c}{}{
\includegraphics[scale=.35]{images/AlgReverseDelete/AlgReverseDelete2.png}
}

De eerste \class{Edge} in $c$, $(3\rightarrow 4)$ heeft het grootste gewicht. Duidelijk is op de afbeelding te zien dat er inderdaad andere paden tussen 3 en 4 mogelijk zijn. Deze \class{Edge} wordt in figuur~\ref{AlgReverseDelete:Progress2} verwijderd.

\ctable[pos=h!t, botcap, figure, caption={Reverse-delete algoritme}, label={AlgReverseDelete:Progress2}]{c}{}{
\includegraphics[scale=.35]{images/AlgReverseDelete/AlgReverseDelete3.png}
}

In figuur~\ref{AlgReverseDelete:Progress3} bereiken we de \class{Edge} $(5\rightarrow 6)$. Ook deze is niet noodzakelijk om knopen 5 en 6 verbonden te houden en wordt dus verwijderd.

\ctable[pos=h!t, botcap, figure, caption={Reverse-delete algoritme}, label={AlgReverseDelete:Progress3}]{c}{}{
\includegraphics[scale=.35]{images/AlgReverseDelete/AlgReverseDelete4.png}
}

In figuur~\ref{AlgReverseDelete:Progress4} zien we \class{Edge} $(1\rightarrow 3)$. Duidelijk is $1\rightarrow 0\rightarrow 3$ een alternatief pad. We verwijderen ook deze \class{Edge}.

\ctable[pos=h!t, botcap, figure, caption={Reverse-delete algoritme}, label={AlgReverseDelete:Progress4}]{c}{}{
\includegraphics[scale=.35]{images/AlgReverseDelete/AlgReverseDelete5.png}
}

%TEMP
\newpage
Als we nogmaals figuur~\ref{AlgReverseDelete:Progress4} bekijken, merken we na $(1\rightarrow 3)$ ook $(5\rightarrow 6)$ op. Echter, deze \class{Edge} is duidelijk de enige die deze twee knopen met elkaar verbindt. In figuur~\ref{AlgReverseDelete:Progress5} merken we op dat de log een bericht bevat dat deze \class{Edge} inderdaad niet verwijderd is. Tot slot wordt $(1\rightarrow 2)$ verwijderd.

\ctable[pos=h!t, botcap, figure, caption={Reverse-delete algoritme}, label={AlgReverseDelete:Progress5}]{c}{}{
\includegraphics[scale=.35]{images/AlgReverseDelete/AlgReverseDelete6.png}
}

In figuur~\ref{AlgReverseDelete:Progress6} merken we op dat $(4\rightarrow 5)$ zonder problemen verwijderd mag worden.

\ctable[pos=h!t, botcap, figure, caption={Reverse-delete algoritme}, label={AlgReverseDelete:Progress6}]{c}{}{
\includegraphics[scale=.35]{images/AlgReverseDelete/AlgReverseDelete7.png}
}

%TEMP
\newpage
Tot slot merken we in figuur~\ref{AlgReverseDelete:Progress7} op dat de volledige inhoud van $c$ in figuur~\ref{AlgReverseDelete:Progress6} bestond uit \class{Edge}s die noodzakelijk waren on de knopen onderling verbonden te houden. In de log zien we dus ook dat voor al deze \class{Edge}s besloten is dat zij de enigen waren die hun knopen verbonden. De getoonde graaf is nu de MST van de begingraaf.

\ctable[pos=h!t, botcap, figure, caption={Reverse-delete algoritme}, label={AlgReverseDelete:Progress7}]{c}{}{
\includegraphics[scale=.35]{images/AlgReverseDelete/AlgReverseDelete8.png}
}

% \chapter{Bespreking programma}\label{Text:Programma}
% //Titel van hoofdstuk moet nog veranderd worden
% \\//Terugkomen op doelstellingen hoofdstuk
% \\//Ieder punt bespreken in detail
% \\//Tekortkomingen bespreken

















\chapter{Gebruikte ADTs}\label{Text:ADTs}
In dit hoofdstuk zullen de gebruikte ADTs in grote lijnen overlopen worden. Alles wat hier besproken wordt is in meer detail ook te vinden in appendix~\ref{Appendix:Doxygen}, welke de Doxygen documentatie voor dit project bevat.

Enkele van deze ADTs zijn gericht tot de gebruiker en zullen ook vanuit een dergelijk standpunt toegelicht worden. ADTs die meer voor intern gebruik dienen worden meer algemeen besproken.

\section{Graph}\label{Text:ADTs:Graph}
\ctable[pos=h!t, figure, botcap, caption={Graph}, label={Dia:Graph}]{c}{}{\includegraphics[scale=.35]{images/Dia/Graph.png}}

Een eerste ADT van groot belang voor de gebruiker is de \class{Graph} module. Deze bevat de volledige implementatie die gebruikt wordt om een graaf te representeren. In hoofdstuk~\ref{Text:Doelstellingen} werden vier doelstellingen voorgesteld met betrekking tot grafen. Hieronder worden deze herhaald:

\begin{enumerate}
\item Elk mogelijk type graaf voorstellen.
\item Een zo bruikbaar, maar nog steeds algemeen mogelijke interface bieden voor het werken met grafen.
\item Wijzigingen in de structuur van de graaf kunnen weergeven.
\item[6.] Bijhouden hoeveel de gebruikte structuren gequeried worden, zodat de gebruiker een beeld krijgt van de complexiteit van het algoritme.
\end{enumerate}

Met deze doelstellingen in het achterhoofd zijn de ADTs in figuur~\ref{Dia:Graph} opgesteld.

Belangrijk was dat elk mogelijk type graaf voorgesteld kan worden; het moet mogelijk zijn een gerichte of ongerichte graaf voor te stellen, een met of zonder bogen die een knoop met zichzelf verbinden, een waar meer dan een boog twee dezelfde knopen kan verbinden, etc. Om bogen toch uit elkaar te kunnen houden is aan de bogen en knopen steeds een identifier gegeven. Deze identifier is uniek voor de graaf waarin zij gecre\"eerd is.

Vanwege dit identifier-systeem zijn de constructors voor \class{Node} en \class{Edge} private gehouden. De enige manier waarop men een van deze structuren aan kan maken is door de aanroep van een functie op de \class{Graph}.

We merken op in figuur~\ref{Dia:Graph} dat er, vanwege dit identifier-systeem, twee mogelijke manieren zijn om de graaf te queryen voor een knoop of boog. Ofwel bij volgnummer ofwel bij identifier. De eerste methode is vooral handig indien ge\"itereerd moet worden over ofwel alle knopen ofwel alle bogen. De tweede manier is handig wanneer men naar \'e\'en specifieke knoop of boog op zoek is.

Aan de derde doelstelling wordt voldaan, want bij iedere wijziging van de structuur van de graaf, wordt een \class{Action} (sectie~\ref{Text:ADTs:Action}) verzonden naar het \class{Algorithm} (sectie~\ref{Text:ADTs:Algorithm}) dat deze graaf manipuleert. In de GUI wordt deze wijziging dan getoond. Op dezelfde wijze wordt aan de zesde doelstelling voldaan. Ook bij iedere query (zoals \function{Node Graph::node(int i)}), wordt een \class{Action} doorgegeven om deze handeling te representeren.

Tot slot kan men opmerken dat inderdaad aan de eerste twee doelstellingen voldaan is. Ieder type graaf kan voorgesteld worden, en de interface voor een graaf is uiteraard vrij algemeen om dit te kunnen ondersteunen. Er werden geen veronderstellingen gemaakt over een specifiek type graaf dat op deze wijze beter voorgesteld kan worden dan een ander.

\section{Algorithm}\label{Text:ADTs:Algorithm}
\ctable[pos=h!t, figure, botcap, caption={Algorithm}, label={Dia:Algorithm}]{c}{}{\includegraphics[scale=.35]{images/Dia/Algorithm.png}}

Een ander belangrijk ADT voor de gebruiker is \class{Algorithm}. \class{Algorithm} is belangrijk omdat de gebruiker deze klasse nodig heeft om een degelijke visualizatie voor een algoritme te kunnen implementeren. Het klassendiagram voor deze module wordt getoond in figuur~\ref{Dia:Algorithm}.

Als een gebruiker zelf een algoritme wil schrijven om door het programma uit te laten voeren, dan moet hij een eigen klasse afleiden van \class{Algorithm}. Het daadwerkelijke algoritme dient uitgevoerd te worden in de \function{run()} functie. De gehele module dient er voor de gebruiker te ondersteunen, en buiten dat ook informatie te winnen over het algoritme dat uitgevoerd wordt.

Om aan deze informatie te raken, wordt van de gebruiker verwacht dat hij gebruik zal maken van het \class{Container}-systeem wat via \class{Algorithm} beschikbaar is, in plaats van de data die het algoritme gebruikt op te slaan in een ander type lijst. In figuur~\ref{Dia:Algorithm} kan men zien hoe containers aangemaakt en gebruikt kunnen worden.

Zodra men toegang heeft tot een \class{Container}, kan men hier \class{ContainerElement}s aan toevoegen en hier de gewenste data in opslaan. De data die hier opgeslagen wordt zal door de GUI getoond worden, en eventuele knopen en bogen die hier opgeslagen zijn kunnen gemarkeerd worden in de GUI. Ook kan via deze module manueel aangegeven welke boog of knoop op een gegeven moment geaccentueerd dient te worden.

De doelstellingen in hoofdstuk~\ref{Text:Doelstellingen} hebben ook betrekking op deze module. Hieronder worden de belangrijkste herhaald:

\begin{enumerate}
\item[4.] Een zo algemeen mogelijk lijst-type aanbieden dat de gebruiker kan benutten om informatie in op te slaan. Dit zal gebruikt moeten kunnen worden om bijvoorbeeld knopen, bogen, getallen, etc op te kunnen slaan. Het programma zal het gebruik hiervan kunnen benutten om informatie over het algoritme te winnen.
\item[5.] Aan de gebruiker toelaten tijdens de voortgang van het algoritme een specifieke knoop of boog manueel te markeren om op deze manier informatie over het algoritme te communiceren. 
\item[7.] Aan de gebruiker toelaten tijdens de uitvoering van zijn zelfgeschreven algoritme commentaar te geven op de gevolgde stappen en dit weer te geven.
\end{enumerate}

Door het gebruik van het \class{Container}-systeem is aan de vierde doelstelling voldaan. Om ook aan de vijde doelstelling te voldoen is een functie \function{void Algorithm::\-highlight(const Node \&node)} voorzien. Van deze functie is ook een variant voor bogen. Tot slot is aan de zevende doelstelling voldaan door de \function{void Algorithm::\-comment( QString c )} aan te bieden. De gebruiker kan deze benutten om commentaar output te doen die dan getoond wordt in het witte vlak in figuur~\ref{App:Interface5}.

\section{Action}\label{Text:ADTs:Action}
\ctable[pos=h!t, figure, botcap, caption={Action}, label={Dia:Action}]{c}{}{\includegraphics[scale=.35]{images/Dia/Action.png}}

De \class{Action} module is zeer belangrijk voor het winnen van informatie. De gebruiker zal hier echter zelf niet veel van zien, maar subklassen van \class{Action} zijn sterk verwoven doorheen de vorige twee modules. Bij bijna iedere handeling zal een \class{Action} doorgegeven worden naar een lijst in \class{Algorithm}, die later aan de GUI verder doorgegeven kan worden. Het klassediagram voor \class{Action} wordt getoond in figuur~\ref{Dia:Action}. Om een goed overzicht te krijgen van tot wat het \class{Action} systeem in staat is is ook in figuur~\ref{Dia:ActionInherit} een inheritance diagram voor deze klasse getoond.

In figuur~\ref{Dia:Action} kan men zien dat \class{Action} op zich geen zeer uitgebreide klasse is. Zeer belangrijk is echter de functie \function{void Action::\-exec( ActionCommunicator* )}, vanwaar een afhankelijkheid van \class{ActionCommunicator} opgebouwd wordt. Deze functie dient door alle subklassen geherimplementeerd te worden. Dit is het punt waarop de specifieke actie via de \class{ActionCommunicator} naar de GUI gecommuniceerd wordt.

\class{ActionCommunicator} op zich heeft geen enkele afhankelijkheid van de GUI. Het functioneert voor iedere functie die zij heeft zeer simpel. Na een call van een functie wordt er een signal ge-emit. Wat er met dit signaal gebeurt is verder voor deze klasse niet van belang, maar de GUI dient deze op te vangen om te tonen wat er door de gegeven actie bedoeld werd. Er is specifiek voor een dergelijk design gekozen om de koppeling tussen GUI en basis zo los mogelijk te houden.

Men kan in figuur~\ref{Dia:Action} opmerken dat \class{ActionCommunicator} een \class{Visualization\-Settings} klasse bevat. Deze wordt gebruikt door \class{Action} om eventueel te beslissen wat wel en niet naar de GUI gecommuniceerd dient te worden.

\ctable[pos=h!t, figure, botcap, caption={Action inheritance}, label={Dia:ActionInherit}]{c}{}{\includegraphics[scale=.5]{images/Dia/ActionInherit.png}}

\section{DOT}\label{Text:ADTs:DOT}
\ctable[pos=h!t, figure, botcap, caption={DOT}, label={Dia:DOT}]{c}{}{\includegraphics[scale=.5]{images/Dia/DOT.png}}

De DOT module heeft als verantwoordelijkheid een representatie van de huidige graaf in de DOT taal te beheren. Deze module staat op zich, zonder afhankelijkheid van de GUI of van andere klassen, maar wordt hoofdzakelijk door de GUI gebruikt. Haar klassediagram wordt getoond in figuur~\ref{Dia:DOT}.

De \class{DManager} wordt ge\"initialiseerd met als parameter een geldige string over de DOT taal, die aan enkele voorwaarden voldoet zodat ze gemakkelijk te parsen is. Informatie over alle knopen en bogen in de graaf wordt in de DEdgeData en DNodeData klassen geparsed, en aan het einde van de rit hebben we een systeem dat deze string op een degelijke manier kan beheren.

Gezien knopen en bogen bepaalde parameters in gemeen kunnen hebben (kleur, label, etc) zijn ze beide afgeleid van de basisklasse \class{DCommonData}. Deze basisklasse is verantwoordelijk van een deel van het initi\"ele parsing, en later voor aanpassing van de parameters indien nodig. Deze module draait volledig rond string manipulatie en zal daarom verder niet in meer detail besproken worden.

\section{Plugins}\label{Text:ADTs:Plugins}
\ctable[pos=h!t, figure, botcap, caption={Plugin}, label={Dia:Plugin}]{c}{}{\includegraphics[scale=.5]{images/Dia/Plugin.png}}

Alhoewel deze sectie niet zo zeer een module beschrijft, kan een plugin eventueel wel zo opgevat worden. Hieronder in figuur~\ref{Dia:Plugin} wordt het klassediagram voor een standaard plugin getoond.

In figuur~\ref{Dia:Plugin} ziet men het ontwerp voor een plugin. Ten eerste maakt de gebruiker een afgeleide klasse van \class{Algorithm} (hier \class{AlgExample}). Zodra deze klasse ge\"implementeerd is, leidt men een klasse af van \class{AlgorithmInterface} (hier \class{AlgExamplePlugin}). Men merkt op dat \class{AlgorithmInterface} afhankelijk is van \class{Algorithm} en analoog ook \class{AlgExamplePlugin} van \class{AlgExample}.

Voor dit design is gekozen om de door de gebruiker ge\"implementeerde representatie van een algoritme zo algemeen mogelijk te houden, maar nog steeds bruikbaar bij het programma. Er worden geen parameters aan de \function{run()} functie doorgegeven, maar eventueel kan de gebruiker wel aanroepen doen naar Qt functies om eventueel input van de gebruiker te verkrijgen.

\section{GUI}\label{Text:ADTs:GUI}
\ctable[pos=h!t, figure, botcap, caption={GUI}, label={Dia:GUI}]{c}{}{\includegraphics[scale=.35]{images/Dia/GUI.png}}

Gezien de GUI inhoudelijk gezien minder interessant is, zal deze in minder detail besproken worden. Het klassediagram in figuur~\ref{Dia:GUI} is zeer onvolledig, maar voldoende om grofweg een beeld te kunnen scheppen van hoe de GUI aan de applicatie gehaakt wordt.

In figuur~\ref{Dia:GUI} beschouwen we eerst de \class{MainWindow}, de bovenste laag van de GUI. Deze is verantwoordelijk voor het beheren van \class{AlgorithmInterface}s, plugins dus. Ook bevat zij een \class{Visualizer}. Zodra de gebruiker dit aangeeft, genereert zij via de \class{AlgorithmInterface} een \class{Algorithm} en geeft dit door aan de \class{Visualizer} die op haar beurt een nieuwe instantie van een \class{Algorithm\-Visuali\-zer} aan zal maken.

De \class{AlgorithmVisualizer} is verantwoordelijk voor het visualizeren van het algoritme specifiek aan die instantie. Bij creatie maakt zij ook een \class{Graph\-Visuali\-zer}, \class{ContainerVisualizer}, \class{GraphAccessWidget} en een \class{AlgorithmLog\-Area} aan.

De \class{GraphVisualizer} bevat een \class{DManager} die op haar beurt de \class{Action\-Com\-muni\-cator} bevat. Beide klassen zorgen er voor dat de signalen van de \class{ActionCommunicator} verbonden zijn met slots in de klassen die deze signalen afhandelen.

Op dit punt kan het GUI systeem een algoritme als volgt visualizeren. \class{AlgorithmVisualizer} popt een \class{Action} uit de lijst beheerd door \class{Algorithm}. Met deze \class{Action} als argument wordt de functie \function{void update( Action* )} aangeroepen op de \class{GraphVisualizer}. Tot slot roept \class{GraphVisualizer} de \function{exec()} functie aan op gegeven \class{Action} met \class{ActionCommunicator} als argument. Als resultaat hiervan zal de \class{ActionCommunicator} \'e\'en of meerdere signalen versturen die door de respectievelijke delen van de GUI verder afgehandeld worden.

\chapter{Visualizaties}\label{Text:Visualizaties}
In dit hoofdstuk zullen alle meegeleverde plugins en hun visualizaties besproken worden. Dit echter in minder detail dan in hoofdstuk~\ref{Text:Plugin}. Een beperkt aantal problemen zal ieder in een eigen sectie besproken worden, met daaropvolgend de betreffende algoritmes die dit probleem oplossen.

\section{Minimum spanning tree}
Het eerste probleem is dat van het vinden van de minimale omspannende boom van een graaf. Dit probleem is eerder besproken in hoofdstuk~\ref{Text:Inleiding:Visualizatie:Kruskal}. Voor met gemak wordt de probleemdefinitie hieronder herhaald.

"Gegeven een gewogen graaf\footnote{Gewogen graaf: Een graaf waarvan alle bogen een gewicht hebben.}, verwijder zoveel mogelijk paden uit deze graaf als mogelijk, terwijl de knopen zelf allen onderling verbonden blijven. De som van alle gewichten van de bogen moet in dit resultaat minimaal zijn".

\subsection{Prim's algoritme}
Het algoritme van Prim kan gedefini\"eerd worden als volgt in listing~\ref{Alg:Prim}. Merk op dat dit algoritme een graaf vereist die geen losse knopen bevat.
\begin{lstlisting}[language={}, label={Alg:Prim}, caption={Prim's Algoritme}]
Initialiseer de op te bouwen MST als de lege boom; initialiseer een verzameling knopen $U$ als een singleton bestaande uit een willekeurige knoop van de graaf.
Zoek een goedkoopste boog tussen een knooppunt in $U$ en een knooppunt buiten $U$. Voeg deze boog toe aan de op te bouwen MST en voeg het knooppunt buiten $U$ toe aan $U$.
Herhaal stap 2 totdat $U$ alle knopen van de graaf bevat.
\end{lstlisting}
In de implementatie van dit algoritme zal de MST voorgesteld worden door een container. Deze zelfde container zal ook gebruikt worden om $U$ voor te stellen, de knopen die al door bogen in de MST verbonden zijn. Dit laatste vooral voor visualizatie-redenen, een \function{bool seen[]} zal eveneens gebruikt worden om gemakkelijker toegang te hebben tot welke knopen al in de MST zitten of nog niet.

\subsubsection{Implementatie}
In pseudocode kan de implementatie van dit algoritme dan voorgesteld worden als in listing~\ref{Pseudo:Prim}.
\begin{lstlisting}[language={}, label={Pseudo:Prim}, caption={Pseude implementatie Prim's Algoritme}]
Gebruik %\'e\'en) Container $cont$.
Gebruik een array van booleans $seen$ met grootte $n$ en initialiseer deze op false.
Voeg node 0 toe aan $cont$ en zet $seen[0]$ op $true$.

Zo lang het ons lukt om knopen toe te voegen aan $cont$...
	Noem $e_{min}$ de minimale Edge.
	
	Voor alle edges...
		Indien $e_{min}$ al gedefinieerd is en de kost van $e$ groter is dan $e_{min}$...
			Sla deze edge $e$ over en ga verder in 8.
		
		Indien de huidige edge $e$ van een knoop in $seen$ vertrekt en in een knoop buiten $seen$ aankomt (of andersom)...
			$e_{min}=e$
	
	Indien $e_{min}$ gedefinieerd is...
		Voeg $e_{min}$ toe aan $cont$, alsook de knoop die nog niet in $seen$ gemarkeerd was.
		Zet $seen$ op $true$ voor de toegevoegde knoop.

Ieder element van $seen$ is nu $true$.
$cont$ bevat de gezochte MST.
\end{lstlisting}

Deze pseudocode kan vrij gemakkelijk omgezet worden in een algoritme. Stap voor stap worden stukjes code toegevoegd en besproken. In listing~\ref{Code:Prim1} ziet men de constructor en destructor voor deze klasse. Men merkt op dat hier enkel \'e\'en \class{Container} aangemaakt hoeft te worden.

\begin{lstlisting}[caption={AlgPrim.cpp: Constructor}, label={Code:Prim1}]
#include"AlgPrim.h" 

AlgPrim::AlgPrim( Graph *g ): Algorithm( g ){
//Gebruik %\'e\'en) Container.
	containerAdd();
}

AlgPrim::~AlgPrim(){
	
}
\end{lstlisting}

Nu kunnen we meteen ook de \function{run()} functie bekijken. Listing~\ref{Code:Prim2} toont de initialisatie-fase.

\begin{lstlisting}[caption={AlgPrim.cpp: Initialisatie}, label={Code:Prim2}]
void AlgPrim::run(){
	//Gebruik %\'e\'en) Container $cont$.
	Container &cont = container(0);
	
	//Gebruik een array van booleans $seen$ met grootte $n$ en initialiseer deze op false.
	int n = graph()->numNodes();
	bool *seen = new bool[n];
	for( int i = 0; i < n; i++ )
		seen[i] = false;
	
	//Voeg node 0 toe aan $cont$ en zet $seen[0]$ op $true$.
	cont.push_back( (new ContainerElement)->setNode(graph()->node(0)) );
	seen[0] = true;
\end{lstlisting}

Na de zeer voordehandliggende initialisatie in listing~\ref{Code:Prim2} kunnen we aan de loop beginnen. Het eerste deel van deze loop zal getoond worden in listing~\ref{Code:Prim3}. Dit zijn regels 8--13  van de pseudocode in listing~\ref{Pseudo:Prim}.

\begin{lstlisting}[label={Code:Prim3}, caption={AlgPrim.cpp: $e_{min}$}]
Zo lang het ons lukt om knopen toe te voegen aan $cont$... ($success$).
	bool success = true;
	while( success ){
		success = false;
		int i = -1;
		int min = -1;
		
		//Noem $e_{min}$ de minimale Edge. (hier: $e_{min}.identifier() == i$).
		//Hiervoor bekijken we alle Edges
		for( int j = 0; j < graph()->numEdges(); j++ ){
			const Edge &e = graph()->edge(j);
			
			//Hebben we al een Edge gevonden en weegt de huidige zwaarder dan deze, dan negeren we de huidige.
			if( success && e.label().toInt() >= min )
				continue;
			
			//Anders moet de huidige Edge minder wegen dan het lichtste tot nu toe.
			//Indien deze Edge een knoop binnen $U$ met een buiten $U$ verbindt...
			if( seen[e.from().identifier()] && !seen[e.to().identifier()] ){
				success = true;
				min = e.label().toInt();
				i = j;
			
			//Indien deze Edge een knoop binnen $U$ met een buiten $U$ verbindt...
			}else if( seen[e.to().identifier()] && !seen[e.from().identifier()] ){
				success = true;
				min = e.label().toInt();
				i = j;
			}
		}
		//Op dit moment...
		//if success == false
		//	Geen Edge werd gevonden.
		//if success == true
		//	Een Edge werd gevonden die een knoop binnen $U$ met een daarbuiten verbindt.
\end{lstlisting}

Nu we $e_{min}$ gevonden hebben en deze aan onze voorwaarden voldoet, kunnen we deze \class{Edge} aan de MST ($cont$) toevoegen. Dit gebeurt in listing~\ref{Code:Prim4}. Merk op dat hier de loop \function{while( success )} be\"eindigd wordt.

\begin{lstlisting}[label={Code:Prim4}, caption={AlgPrim.cpp: Opbouwen MST}]
		if( success ){
			const Edge &e = graph()->edge(i);
			if( seen[e.from().identifier()] ){
				cont.push_back( (new ContainerElement)->setNode(e.to())->setEdge(e) );
				seen[e.to().identifier()] = true;
			}else{
				cont.push_back( (new ContainerElement)->setNode(e.from())->setEdge(e) );
				seen[e.from().identifier()] = true;
			}
		}
	}
\end{lstlisting}

In listing~\ref{Code:Prim4} wordt de code getoond die zowel de huidige \class{Edge} als de nieuwe \class{Node} aan de MST toevoegt. Aan het einde van de while loop zal de gebruikte \class{Container} de volledige MST bevatten. Om dit visueel meer aantrekkelijk weer te geven, worden aan het einde alle \class{Edge}s verwijderd die niet tot de MST behoren. Dit wordt getoond in listing~\ref{Code:Prim5}.

\begin{lstlisting}[label={Code:Prim5}, caption={AlgPrim.cpp: Tonen MST}]
	//Voor iedere Edge in de graaf.
	for( int i = 0; i < graph()->numEdges(); i++ ){
		const Edge &e = graph()->edge(i);
		
		//Als zij in de Container (MST) zit, moet zij behouden worden
		bool shouldKeep = false;
		for( int j = 1; j < cont.size() && !shouldKeep; j++ )
			shouldKeep = e == *cont[j]->edge();
		
		//Moet ze niet behouden worden, dan wordt ze verwijderd.
		if(!shouldKeep){
			graph()->removeEdge(e);
			i--;
		}
	}
}
\end{lstlisting}

\newpage
\subsubsection{Visualizatie}
De visualizatie van het verloop van dit algoritme zal dan gaan als volgt.

\ctable[pos=h!t, figure, botcap, caption={Prim's Algoritme}, label={AlgPrim:exec1}]{c}{}{\includegraphics[scale=.5]{images/AlgPrim/AlgPrim1.png}}

In figuur~\ref{AlgPrim:exec1} ziet men de startgraaf. Het algoritme is ge\"initialiseerd met knoop $0$ (label $A$) toegevoegd aan $cont$. Men merkt op dat er op dit moment \'e\'en query op de graaf is gebeurd om knoop $0$ te selecteren.

\newpage
\ctable[pos=h!t, figure, botcap, caption={Prim's Algoritme}, label={AlgPrim:exec2}]{c}{}{\includegraphics[scale=.5]{images/AlgPrim/AlgPrim2.png}}

In de vorige figuur kon men twee paden van knoop $0$ zien. Het pad met de laagste kost, pad $0\rightarrow 3$, is in figuur~\ref{AlgPrim:exec2} toegevoegd aan $cont$. Men merkt op dat er op dit moment twaalf maal een query op de graaf is gebeurd om de edges te doorlopen. De graaf heeft 11 edges, en er is \'e\'en extra query gebeurd om de $e_{min}$ toe te voegen aan $cont$.

\newpage
\ctable[pos=h!t, figure, botcap, caption={Prim's Algoritme}, label={AlgPrim:exec3}]{c}{}{\includegraphics[scale=.5]{images/AlgPrim/AlgPrim3.png}}

In figuur~\ref{AlgPrim:exec3} wordt het programma getoond na afloop van het eigenlijke algoritme. Men kan opmerken dat er op dit moment 72 queries op de edges van de graaf gebeurd zijn. Dit is gelijk aan $6\times 12$ ofwel $(n-1) \times (\#edges+1)$. Men kan zien dat $cont$ nu daadwerkelijk de MST bevat. Elke knoop van de graaf is hier aan toegevoegd en ze zijn allen met elkaar verbonden. De inhoud van $cont$ is rood gemarkeerd op de graaf.

\newpage
\ctable[pos=h!t, figure, botcap, caption={Prim's Algoritme}, label={AlgPrim:exec4}]{c}{}{\includegraphics[scale=.5]{images/AlgPrim/AlgPrim4.png}}

Figuur~\ref{AlgPrim:exec4} toont het programma na afloop van het totale algoritme. Hier wordt enkel de MST nog getoond; alle overige edges zijn nu verwijderd.


\subsection{Boruvka's algoritme}
Het algoritme van Boruvka\cite{boruvka} vereist ook van een graaf dat zij geen losse knopen bevat. Ook vereist het algoritme dat de gewichten van de bogen onderling verschillend zijn. In pseudocode wordt het getoond in listing~\ref{Pseudo:Boruvka}.

\begin{lstlisting}[label={Pseudo:Boruvka}, caption={Boruvka's algoritme}, language={}]
Neem een graaf $G$ en een lege verzameling bogen $T$.
Zolang de knopen van $G$ verbonden door $T$ nog niet allemaal onderling verbonden zijn...
	Neem een lege verzameling bogen $E$.
	Voor iedere deelboom, doe...
		Neem een lege verzameling $S$.
		Voor iedere knoop in deze deelboom...
			Voeg de goedkoopste boog vanuit deze knoop die deze deelboom met een andere verbindt toe aan $S$.
		Voeg de goedkoopste boog in $S$ toe aan $E$.
	Voeg alle bogen in $E$ toe aan $T$.
$T$ bevat nu alle bogen van de MST.
\end{lstlisting}
\subsubsection{Implementatie}
Om dit algoritme te implementeren gebruiken we de verzameling van alle containers om $T$ voor te stellen. We initialiseren deze met in iedere \class{Container} \'e\'en \class{Node}. Zodra twee van deze `deelbomen' verbonden worden door een \class{Edge}, wordt deze aan de \class{Container} toegevoegd en worden de rest van de elementen van de \class{Container} samengevoegd. De structuren $E$ en $S$ zullen blijven zoals in de pseudocode van listing~\ref{Pseudo:Boruvka}.

In pseudocode kan de implementatie voorgesteld worden zoals in listing~\ref{Code:Boruvka1}.

\begin{lstlisting}[label={Code:Boruvka1}, caption={Boruvka's algoritme}, language={}]
$\forall n \in G$ doe{
	Maak een nieuwe container $c$ aan.
	Voeg $n$ toe aan $c$.
}

Zolang #containers $\not = 1$ doe{
	Neem een lege lijst van bogen $E$.
	Voor alle containers $c$ (= deelbomen) doe{
		Neem een lege lijst van bogen $S$.
		Voor alle knopen $n$ in $c$ doe{
			Voeg de goedkoopste boog $e$ vanuit $n$ naar een andere deelbom toe aan $S$.
		}
		Voeg de goedkoopste boog $e$ van $S$ toe aan $E$.
	}
	Voor alle bogen $e$ in $E$ doe{
		Voeg de elementen van de containers die $e.from()$ en $e.to()$ bevatten samen.
		Verwijder de lege container.
	}
}
Nu rest er nog %\'e\'en) container die precies de MST bevat.
\end{lstlisting}

Men kan zien dat de stap van listing~\ref{Pseudo:Boruvka} naar listing~\ref{Code:Boruvka1} grotendeels draait rond het toevoegen van het gebruik van containers. Voor de rest is er niet veel veranderd. Merk op in regel 16 dat $e$ niet noodzakelijk uniek is en dat het mogelijk is dat $e.from()$ en $e.to()$ in dezelfde container zitten. In dit geval wordt het samenvoegen simpelweg niet uitgevoerd zonder verder een invloed op het verloop van het algoritme te hebben.

Constructor en destructor voor deze klasse zullen leeg zijn. Enkel de \function{run()} functie en enkele andere gedefini\"eerde functies moeten dus besproken worden. Voor het gemak is een functie \function{int containerContaining( const Node \&n )} gedefini\"eerd. Deze wordt getoond in listing~\ref{Code:Boruvka2}.

\begin{lstlisting}[label={Code:Boruvka2}, caption={AlgBoruvka.cpp: containerContaining()}]
int AlgBoruvka::containerContaining( const Node &n ){
	for( int i = 0; i < containerCount(); i++ ){
		for( int j = 0; j < container(i).size(); j++ ){
			if( *container(i)[j]->node() == n )
				return i;
		}
	}
	return -1;
}
\end{lstlisting}

De code in listing~\ref{Code:Boruvka2} zou zeker geen verrassing moeten zijn. Ook wordt er een functie \function{static inline void swap( int \&a, int \&b )} gebruikt. Deze wisselt simpelweg de waarden in variabelen $a$ en $b$ om. Tot slot is er nog \'e\'en functie \function{void merge( int src, int dst, const Edge \&e )} gedefini\"eerd die getoond zal worden in listing~\ref{Code:Boruvka3}. Deze functie zal containers $src$ en $dst$ samenvoegen en $e$ hier ook in opslaan, gezien $e$ deze twee deelbomen verbindt en dus tot de MST zal behoren.

\begin{lstlisting}[label={Code:Boruvka3}, caption={AlgBoruvka.cpp: merge()}]
//Voeg containers $src$ en $dst$ samen.
void AlgBoruvka::merge( int src, int dst, const Edge &e ){
	//Als dit dezelfde containers zijn stoppen we.
	if( src == dst ){
		return;
	}
	
	//We maken $dst$ de container met laagste volgnummer. Als resultaat hiervan zal uiteindelijk de MST in container $0$ terecht komen.
	if( src < dst )
		swap(src, dst);
	
	//Voeg de containers samen
	while( container(src).size() > 0 ){
		container(dst).push_back( container(src).takeAt(0) );
	}
	
	//Sla Edge $e$ op in de eerste vrije locatie.
	for( int i = 0; i < container(dst).size(); i++ ){
		if( container(dst)[i]->edge() == 0 ){
			container(dst)[i]->setEdge(e);
			break;
		}
	}
	
	//Verwijder eventuele lege containers.
	while(true){
		if( container( containerCount()-1 ).size() == 0 )
			containerPop();
		else
			break;
	}
}
\end{lstlisting}

Nu alle ondersteunende functies toegelicht zijn, kan in listing~\ref{Code:Boruvka4} de \function{run()} functie getoond worden.
% $\forall n \in G$ doe{
% 	Maak een nieuwe container $c$ aan.
% 	Voeg $n$ toe aan $c$.
% }
% 
% Zolang #containers $\not = 1$ doe{
% 	Neem een lege lijst van bogen $E$.
% 	Voor alle containers $c$ (= deelbomen) doe{
% 		Neem een lege lijst van bogen $S$.
% 		Voor alle knopen $n$ in $c$ doe{
% 			Voeg de goedkoopste boog $e$ vanuit $n$ naar een andere deelbom toe aan $S$.
% 		}
% 		Voeg de goedkoopste boog $e$ van $S$ toe aan $E$.
% 	}
% 	Voor alle bogen $e$ in $E$ doe{
% 		Voeg de elementen van de containers die $e.from()$ en $e.to()$ bevatten samen.
% 		Verwijder de lege container.
% 	}
% }
% Nu rest er nog %\'e\'en) container die precies de MST bevat.
\begin{lstlisting}[label={Code:Boruvka4}, caption={AlgBoruvka.cpp: run()}]
void AlgBoruvka::run(){
	//$\forall n \in G$ doe
	for( int i = 0; i < graph()->numNodes(); i++ ){
		//Maak een nieuwe container $c$ aan.
		containerAdd();
		
		//Voeg $n$ toe aan $c$.
		container(i).push_back( (new ContainerElement)->setNode(graph()->node(i)) );
	}
	
	//Zolang #containers $\not = 1$ doe
	while( containerCount() > 1 ){
		
		//Neem een lege lijst van bogen $E$.
		QList<Edge> E;
		
		//Voor alle containers $c$ (= deelbomen) doe
		for( int i = 0; i < containerCount(); i++ ){
			
			//Neem een lege lijst van bogen $S$.
			QList<Edge> S;
			
			//Voor alle knopen $n$ in $c$ doe
			for( int j = 0; j < container(i).size(); j++ ){
				
				//Voeg de goedkoopste boog $e$ vanuit $n$ naar een andere deelbom toe aan $S$.
				//$from$ bevat alle bogen vanuit $n$.
				QList<Edge> from = graph()->edgesFrom( *container(i)[j]->node() );
				
				//We verwijderen alle bogen uit $n$ die $n$ verbinden met een knoop in dezelfde deelboom.
				for( int k = 0; k < from.size(); k++ ){
					const Edge &e = from[k];
					if( containerContaining(e.from()) == containerContaining(e.to()) ){
						from.removeAt(k);
						k--;
					}
				}
				
				//Als $from$ leeg is, gaan we verder met een andere knoop.
				if( from.size() == 0 ){
					continue;
				}
				
				//Alle bogen in $from$ verbinden nu $n$ met een knoop in een andere deelboom.
				//We verwijderen bogen uit $from$ tot de goedkoopste overblijft.
				while( from.size() > 1 ){
					
					if( from[0].label().toInt() > from[1].label().toInt() )
						from.pop_front();
					else
						from.removeAt(1);
				}
				
				//Nu hebben we de goedkoopste boog gevonden en voegen deze toe aan $S$.
				S.push_back(from[0]);
			}
			
			//Voeg de goedkoopste boog $e$ van $S$ toe aan $E$.
			while( S.size() > 1 ){
				if( S[0].label().toInt() > S[1].label().toInt() )
					S.pop_front();
				else
					S.removeAt(1);
			}
			if(S.size() == 1)
				E.push_back(S[0]);
		}
		//Voor alle bogen $e$ in $E$ doe
		while( E.size() > 0 ){
			//Voeg de elementen van de containers die $e.from()$ en $e.to()$ bevatten samen. Verwijder eventueel lege containers.
			merge( containerContaining(E[0].from()), containerContaining(E[0].to()), E[0] );
			
			E.pop_front();
		}
	}
	
	//Nu rest er nog %\'e\'en) container die precies de MST bevat.
	//Voor de verduidelijking verwijderen we alle bogen uit de graaf die niet tot de MST behoren.
	
	for( int i = graph()->numEdges() - 1; i >= 0; i-- ){
		const Edge &e = graph()->edge(i);
		bool found = false;
		for( int j = 0; j < container(0).size() && !found; j++ ){
			found = container(0)[j]->edge() != 0 && *container(0)[j]->edge() == e;
		}
		if( !found )
			graph()->removeEdge(e);
	}
}
\end{lstlisting}

Gezien de pseudocode uit listing~\ref{Code:Boruvka1} volledig herhaald is in listing~\ref{Code:Boruvka4} wordt verondersteld dat de lezer deze code grotendeels begrijpt. Op dit punt kan een visualizatie voor dit algoritme getoond worden.

\subsubsection{Visualizatie}
Nu de implementatie van het algoritme van Boruvka belicht is, kan een visualizatie getoond worden. Dit gebeurt aan de hand van dezelfde graaf die gebruikt werd voor het algoritme van Prim, getoond in figuur~\ref{AlgPrim:exec1} op pagina~\pageref{AlgPrim:exec1}. Na de initialisatie-fase (regels 1--9 in listing~\ref{Code:Boruvka4}) zal men het scherm in figuur~\ref{AlgBoruvka:exec1} te zien krijgen.

\ctable[pos=h!t, figure, botcap, caption={Boruvka's Algoritme}, label={AlgBoruvka:exec1}]{c}{}{\includegraphics[scale=.5]{images/AlgBoruvka/AlgBoruvka2.png}}

Als we nu nogmaals de pseudo-code in listing~\ref{Pseudo:Boruvka} bekijken, kunnen we voorspellen wat er gebeuren zal. Voor iedere deelboom (die op dit moment uit slechts \'e\'en knoop bevat), zal de goedkoopste boog geselecteerd worden die deze knoop met een andere deelbom verbindt. We verwachten dus het volgende:
\begin{itemize}
\item Voor de deelboom in container 0 wordt de boog $0\rightarrow3$ gekozen.
\item Voor 1 wordt de boog $0\rightarrow1$ gekozen.
\item Voor 2 wordt $2\rightarrow4$ gekozen.
\item Voor 3 wordt $0\rightarrow3$ gekozen, maar deze hadden we al.
\item Voor 4 wordt $2\rightarrow4$ gekozen, maar deze hadden we ook al.
\item Voor 5 wordt $3\rightarrow5$ gekozen.
\item Voor 6 wordt $4\rightarrow6$ gekozen.
\end{itemize}

Dat deze verwachting inderdaad correct is wordt getoond in figuur~\ref{AlgBoruvka:exec2}.

\ctable[pos=h!t, figure, botcap, caption={Boruvka's Algoritme}, label={AlgBoruvka:exec2}]{c}{}{\includegraphics[scale=.5]{images/AlgBoruvka/AlgBoruvka7.png}}

In figuur~\ref{AlgBoruvka:exec2} blijven er dus twee deelbomen over. Voor iedere deelboom zal weer \'e\'en boog geselecteerd worden om toe te voegen aan de MST. Beide deelbomen worden in dit geval verwacht de boog $1\rightarrow4$ te kiezen. Dat dit inderdaad correct is ziet men in figuur~\ref{AlgBoruvka:exec3}.

\ctable[pos=h!t, figure, botcap, caption={Boruvka's Algoritme}, label={AlgBoruvka:exec3}]{c}{}{\includegraphics[scale=.5]{images/AlgBoruvka/AlgBoruvka8.png}}
%TEMP
\newpage
Op dit punt in figuur~\ref{AlgBoruvka:exec3} bevat \class{Container} 0 de volledige MST. In de laatste fase van dit algoritme (regels 80--89 in listing~\ref{Code:Boruvka4}) worden de bogen die niet tot de MST behoren nog verwijderd. Dit ziet men in figuur~\ref{AlgBoruvka:exec4}. 

\ctable[pos=h!t, figure, botcap, caption={Boruvka's Algoritme}, label={AlgBoruvka:exec4}]{c}{}{\includegraphics[scale=.5]{images/AlgBoruvka/AlgBoruvka9.png}}

Men kan nu figuur~\ref{AlgBoruvka:exec4} vergelijken met figuur~\ref{AlgPrim:exec4} om te zien dat de gevonden MST's inderdaad identiek zijn.

\subsection{Kruskal's algoritme}
Eerder gepresenteerd in sectie~\ref{Text:Inleiding:Visualizatie:Kruskal} was het algoritme van Kruskal. Haar pseudocode wordt herhaald in listing~\ref{Pseudo:Kruskal}.

\begin{lstlisting}[language={}, label={Pseudo:Kruskal}, caption={Kruskals algoritme}]
Maak een verzameling van bomen $F$, zodat elke knoop van de graaf in %\'e\'en) aparte boom zit.
Maak een verzameling $S$ van alle bogen van de graaf.
Zolang $S$ niet leeg is, doe:
	Verwijder een boog met minimum gewicht uit $S$. Noem deze boog $B$.
	Als $B$ twee verschillende bomen verbindt: 
		Verwijder de twee bomen $b_1$ en $b_2$ uit $F$.
		Verdind $b_1$ en $b_2$ door $B$. Noem het resultaat $b'$.
		Voeg $b'$ toe aan $F$.
$F$ bevat nu slechts %\'e\'en) element, de minimum omspannende boom voor gegeven graaf.
\end{lstlisting}

\subsubsection{Implementatie}
Om de pseudocode in listing~\ref{Pseudo:Kruskal} makkelijker te implementeren te maken, herschrijven we dit deels en introduceren we het gebruik van het container-systeem. Het resultaat ziet men in listing~\ref{Pseudo:Kruskal2}.

\begin{lstlisting}[language={}, label={Pseudo:Kruskal2}, caption={Kruskals algoritme}]
Sorteer alle bogen en voeg deze gesorteerd toe aan container 0.
Voor alle knopen $n$ in $G$ doe
	Maak een nieuwe container aan en voeg $n$ daaraan toe.
Zolang container 0 niet leeg is
	Indien het eerste element $e$ (boog) van container 0 knopen uit twee verschillende containers $a$ en $b$ verbindt doe...
		Voeg alle elementen van $b$ toe aan $a$.
		Verwijder container $b$.
		Voeg $e$ toe aan container $a$ op de eerste vrije plaats.
	Verwijder het eerste element van container 0.
Indien de graaf volledig verbonden was, zal de MST nu in %\'e\'en) container bevat zijn.
\end{lstlisting}

De versie van het algoritme in listing~\ref{Pseudo:Kruskal2} kan nu gemakkelijk stapsgewijs ge\"implementeerd worden. Gezien alle bogen in \'e\'en container bevat worden, wordt in de constructor van de klasse enkel eenmaals \function{containerAdd()} aangeroepen. Eerst zullen de initialisatie- en hulpfuncties getoond worden, tot slot de \function{run()} functie.

\begin{lstlisting}[caption={AlgKruskal.cpp: sortEdges()}, label={Code:Kruskal1}]
//Sorteer alle bogen en voeg deze gesorteerd toe aan container 0.
void AlgKruskal::sortEdges(){
	Container &edges = container(0);
	QList<Edge> E;
	QList<int> C;
	
	//We slaan alle edges en hun respectievelijke kosten op in twee lijsten.
	for( int i = 0; i < graph()->numEdges(); i++ ){
		const Edge &e = graph()->edge(i);
		E.push_back(Edge(e));
		C.push_back(e.label().toInt());
	}
	
	while( E.size()>0 ){
		//Vindt de goedkoopste boog
		int min = C[0];
		int imin = 0;
		for( int i = 1; i < C.size(); i++ ){
			if( C[i] < min ){
				min = C[i];
				imin = i;
			}
		}
		
		//Voeg deze toe aan container 0.
		edges.push_back( (new ContainerElement)->setEdge(E[imin]) );
		E.removeAt(imin);
		C.removeAt(imin);
	}
}
\end{lstlisting}

De code in listing~\ref{Code:Kruskal1} voorziet simpelweg het sorteren van alle bogen van de graaf en het gesorteerd toevoegen van deze aan container 0. Nu moeten enkel nog alle knopen ieder in een aparte container opgeslagen worden en is de initialisatie-fase compleet. Dit wordt getoond in listing~\ref{Code:Kruskal2}.

\begin{lstlisting}[label={Code:Kruskal2}, caption={AlgKruskal.cpp: populateNodes()}]
void AlgKruskal::populateNodes(){
	//Voor alle knopen $n$ in $G$ doe
	for( int i = 0; i < graph()->numNodes(); i++ ){
		//Maak een nieuwe container aan en voeg $n$ daaraan toe.
		containerAdd();
		container( containerCount() - 1 ).push_back( (new ContainerElement)->setNode(graph()->node(i)) );
	}
}
\end{lstlisting}

Ook de code in listing~\ref{Code:Kruskal2} zal niet verbazen. Verder worden ook de functies \function{swap()}, \function{merge()} en \function{containerContaining()} gebruikt in exact dezelfde manier als bij het algoritme van Boruvka. De code voor de laatste twee functies kan gevonden worden in respectievelijk listings~\ref{Code:Boruvka3} en~\ref{Code:Boruvka2}. Op dit punt zijn voldoende ondersteunende functies gedefini\"eerd om het algoritme van Kruskal te kunnen implementeren in de \function{run()} functie in listing~\ref{Code:Kruskal3}.

% Sorteer alle bogen en voeg deze gesorteerd toe aan container 0.
% Voor alle knopen $n$ in $G$ doe
% 	Maak een nieuwe container aan en voeg $n$ daaraan toe.
% Zolang container 0 niet leeg is
% 	Indien het eerste element $e$ (boog) van container 0 knopen uit twee verschillende containers $a$ en $b$ verbindt doe...
% 		Voeg alle elementen van $b$ toe aan $a$.
% 		Verwijder container $b$.
% 		Voeg $e$ toe aan container $a$ op de eerste vrije plaats.
% 	Verwijder het eerste element van container 0.
% Indien de graaf volledig verbonden was, zal de MST nu in %\'e\'en) container bevat zijn.

\begin{lstlisting}[caption={AlgKruskal.cpp: run()}, label={Code:Kruskal3}]
void AlgKruskal::run(){
	//Sorteer alle bogen en voeg deze gesorteerd toe aan container 0.
	sortEdges();
	
	//Voor alle knopen $n$ in $G$ doe
		//Maak een nieuwe container aan en voeg $n$ daaraan toe.
	populateNodes();
	Container &edges = container(0);
	
	//Zolang container 0 niet leeg is
	while( edges.size() > 0 ){
		int src = containerContaining(edges[0]->edge()->from());
		int dst = containerContaining(edges[0]->edge()->to());
		
		//Indien het eerste element $e$ van container 0 knopen uit twee verschillende containers $src$ en $dst$ verbindt doe...
		if( src != -1 && dst != -1 && src != dst ){
		
			//Voeg alle elementen van $src$ toe aan $dst$.
			//Voeg $e$ toe aan container $dst$ op de eerste vrije plaats.
			merge(src, dst, *edges[0]->edge());
		}
		
		//Verwijder het eerste element van container 0.
		delete edges.takeAt(0);
	}
	
	//Indien de graaf volledig verbonden was, zal de MST nu in %\'e\'en) container bevat zijn.
	
	//Om dit te visualizeren worden alle bogen die niet in container 0 bevat zijn uit de graaf verwijderd.
	for( int i = graph()->numEdges() - 1; i >= 0; i-- ){
		const Edge &e = graph()->edge(i);
		bool found = false;
		for( int j = 0; j < container(1).size() && !found; j++ ){
			found = container(1)[j]->edge() != 0 && *container(1)[j]->edge() == e;
		}
		if( !found )
			graph()->removeEdge(e);
	}
}

\end{lstlisting}

\subsubsection{Visualizatie}

De resulterende visualizatie voor dit algoritme wordt besproken in hoofdstuk~\ref{Text:Inleiding:Visualizatie:Kruskal} op pagina~\pageref{AlgKruskal:Exec} en getoond in figuur~\ref{AlgKruskal:Exec}.

\subsection{Reverse-delete algoritme}
Het reverse-delete algoritme werd uitgebreid besproken in hoofdstuk~\ref{Text:Plugin}.

\section{Shortest path}
Een tweede probleem waarvoor algoritmen voorzien zijn is het kortste pad probleem. Hier zijn vele varianten van, zoals het vinden van het kortste pad van $A$ naar $B$, alle kortste paden van $A$ naar alle andere knopen, of alle kortste paden van alle knopen naar alle andere knopen. In essentie lost iedere variant ook automatisch de eerste variant op.

\subsection{A* algoritme}
Het eerste algoritme dat besproken zal worden lost de eerste variant van dit probleem op. Het A* algoritme zoekt het kortste pad van $A$ naar $B$. Dit algoritme kan in pseudocode als volgt in listing~\ref{Pseudo:AStar} beschreven worden.

\begin{lstlisting}[language={}, label={Pseudo:AStar}, caption={A* algoritme}]
Voor alle knopen $n$ %defini\"eer) $n.parent, n.f, n.g$ en $n.h$.
$n.g$ is de afstand van de startknoop tot $n$.
$n.h$ is een schatting van de afstand van $n$ tot de eindknoop.
$n.f$ is een schatting van de afstand van start tot eind over $n$.
$n.parent$ is de knoop via welke $n$ bereikt is.

Neem twee lijsten van knopen $open$ en $closed$.
Voeg de beginknoop toe aan $open$.
Zolang $open$ niet leeg en eindknoop niet gevonden...
	Neem de knoop $n$ de knoop met laagste $n.f$ uit $open$.
	Voeg $n$ toe aan $closed$.
	Indien $n$ de eindknoop, stop hier.
	Voor alle knopen $n'$ die via %\'e\'en) pad met $n$ verbonden zijn...
		Als $n'\in closed$, %be\"eindig) deze stap.
		Als $n'\not\in open$...
			Voeg $n'$ toe aan $open$.
			Zet $n'.parent = n$.
			Bereken $n'.f, n'.g, n'.h$.
		Anders, als $n'\in open$...
			Vergelijk de $n'.g$ via de huidige parent en via $n$.
			Indien via $n$ goedkoper...
				Zet $n'.parent = n$.
				Bereken $n'.f, n'.g, n'.h$.
Indien de eindknoop gevonden was, kan via $n.parent$ het kortste pad gevonden worden.
\end{lstlisting}

Merk op dat de pseudocode in listing~\ref{Pseudo:AStar} relatief ingewikkeld is. Er is nog niets vermeld over hoe de kosten berekend en geschat worden. Hiervoor worden twee veronderstellingen gemaakt:
\begin{itemize}
\item Elk pad bevat in haar label haar kost.
\item Elke knoop bevat in haar label een coordinatenpaar.
\end{itemize}
Nu kan de kost van de paden gebruikt worden om de $g$ component te berekenen. De $h$ kost kan berekend worden door de afstand tussen de huidige en de eindknoop te gebruiken `zoals de vogels vliegen'. De $f$ is dan simpelweg $g+h$.

Merk op dat het belangrijk is aan de schattingsfunctie dat zij nooit schat dat de afstand tussen twee knopen groter is dan ze daadwerkelijk is. Bij het gebruik van co\"ordinaten is aan dit criterium voldaan.

\subsubsection{Implementatie}
In dit geval, gezien de bovenstaande pseudocode al zeer complex is, zal direct de code besproken worden, gezien het grotendeels van deze pseudocode al vertrekt. Eerst worden in listing~\ref{Code:AStar1} twee simpele gebruikte datastructuren getoond, voor de co\"ordinaten en voor de $f, g, h$ en $parentID$ variabelen.

\begin{lstlisting}[label={Code:AStar1}, caption={AlgAStar.h: Coordinates en Data}]
typedef struct str_data{
	str_data( double g = 0.0, double h = 0.0, double f = 0.0, int parentID = -1 ){
		this->f = f;
		this->g = g;
		this->h = h;
		this->parentID = parentID;
	}
	double f;
	double g;
	double h;
	int parentID;
}Data;

typedef struct str_coordinates{
	str_coordinates(double x, double y){
		this->x = x;
		this->y = y;
	}
	str_coordinates( const char *data ){
		sscanf( data, "\"%\%)lf, %\%)lf\"", &x, &y );
	}
	double x;
	double y;
}Coordinates;
\end{lstlisting}

We voorzien ook twee functies \function{Container \&open()} en \function{Container \&closed()} om gemakkelijk en meer intuitief aan twee containers te kunnen komen. De volledige klassedefinitie is te zien in listing~\ref{Code:AStar2}.

\begin{lstlisting}[label={Code:AStar2}, caption={AlgAStar.h: klassedefinitie}]
class AlgAStar: public Algorithm{
public:
	AlgAStar( Graph *g );
	~AlgAStar();
	void run();
	void astar( const Node &start, const Node &dest );
private:
	Container &closed(){ return container(1); }
	QList<Data*> m_closedData;
	
	Container &open(){ return container(0); }
	QList<Data*> m_openData;
	
	const Node *m_dest;
	
	void addToOpenList(const Node &node, int parentID = -1, double g = 0.0);
	void selectFromOpenList();
	double guessDistance( const Node &node );
	inline bool isInClosedList( const Node &n );
	void printRoute( const Node &n, Data *d );
	
	static Node otherNode( const Edge &e, const Node &n );
};
\end{lstlisting}
We merken op in listing~\ref{Code:AStar2} dat een \class{Container} gebruikt wordt voor zowel de open als de closed list, maar tegelijkertijd de bijbehorende \class{Data} opgeslagen wordt in een \class{QList}. Tot slot wordt ook een pointer naar de eindknoop behouden.

In de \function{run()} functie zal simpelweg \function{astar()} aangeroepen worden met twee knopen als parameters, de start- en eindknoop. Zonder veel over de implementaties van de hulpfuncties te weten, kan nu de \function{astar()} functie getoond worden. Dit gebeurt in listing~\ref{Code:AStar3}.

% Neem twee lijsten van knopen $open$ en $closed$.
% Voeg de beginknoop toe aan $open$.
% Zolang $open$ niet leeg en eindknoop niet gevonden...
% 	Neem de knoop $n$ de knoop met laagste $n.f$ uit $open$.
% 	Voeg $n$ toe aan $closed$.
% 	Indien $n$ de eindknoop, stop hier.
% 	Voor alle knopen $n'$ die via %\'e\'en) pad met $n$ verbonden zijn...
% 		Als $n'\in closed$, %be\"eindig) deze stap.
% 		Als $n'\not\in open$...
% 			Voeg $n'$ toe aan $open$.
% 			Zet $n'.parent = n$.
% 			Bereken $n'.f, n'.g, n'.h$.
% 		Anders, als $n'\in open$...
% 			Vergelijk de $n'.g$ via de huidige parent en via $n$.
% 			Indien via $n$ goedkoper...
% 				Zet $n'.parent = n$.
% 				Bereken $n'.f, n'.g, n'.h$.
% Indien de eindknoop gevonden was, kan via $n.parent$ het kortste pad gevonden worden.


\begin{lstlisting}[label={Code:AStar3}, caption={AlgAStar.cpp: astar()}]
void AlgAStar::astar( const Node &start, const Node &dest ){
	m_dest = &dest;
	
	//Voeg de beginknoop toe aan $open$.
	addToOpenList(start);
	
	//Zolang $open$ niet leeg en eindknoop niet gevonden...
	while( open().size() > 0 ){
	
		//Neem de knoop $n$ de knoop met laagste $n.f$ uit $open$.
		//Voeg $n$ toe aan $closed$.
		selectFromOpenList();
		const Node &n = *closed()[0]->node();
		Data *d = m_closedData[0];
		
		//Indien $n$ de eindknoop, stop hier.
		if( n == *m_dest ){
			printRoute( n, d );
			return;
		}
		
		//Voor alle knopen $n'$ die via %\'e\'en) pad met $n$ verbonden zijn...
		QList<Edge> edges = graph()->edgesFrom(n);
		for( int i = 0; i < edges.size(); i++ ){
		
			//Gezien de graaf ongericht kan zijn, is deze functie nodig.
			const Node &other = otherNode(edges[i], n);
			
			//Als $n'\in closed$, %be\"eindig) deze stap.
			if( !isInClosedList( other ) ){
			
				//Als $n'\not\in open$...
				//	Voeg $n'$ toe aan $open$.
				//	Zet $n'.parent = n$.
				//	Bereken $n'.f, n'.g, n'.h$.
				//Anders, als $n'\in open$...
				//	Vergelijk de $n'.g$ via de huidige parent en via $n$.
				//	Indien via $n$ goedkoper...
				//		Zet $n'.parent = n$.
				//		Bereken $n'.f, n'.g, n'.h$.
				addToOpenList( other, n.identifier(), d->g + edges[i].label().toDouble() );
			}
		}
	}
}
\end{lstlisting}
We merken op in listing~\ref{Code:AStar3} dat de getoonde code grotendeels goed met de pseudocode van listing~\ref{Pseudo:AStar} die hier in commentaar getoond wordt overeenkomt. De gebruikte functies zijn echter nog niet besproken. In regels 32--40 merkt men op dat de \function{addToOpenList()} functie een behoorlijk grote verantwoordelijkheid heeft. Deze wordt getoond in listing~\ref{Code:AStar4}.

\begin{lstlisting}[label={Code:AStar4}, caption={AlgAStar.cpp: addToOpenList()}]
void AlgAStar::addToOpenList(const Node &node, int parentID, double g){

	//Eerst worden f, en h berekend, g is meegegeven.
	double h = guessDistance(node);
	double f = g + h;
	bool shouldAdd = true;
	
	shouldAdd = true;
	for( int i = 0; i < open().size() && shouldAdd; i++ ){
	
		//Als $n'\in open$...
		if( *open()[i]->node() == node ){
			
			//Vergelijk de $n'.g$ via de huidige parent en via $n$.
			//Indien via $n$ goedkoper...
			if( m_openData[i]->g > g ){
			
				//Zet $n'.parent = n$.
				m_openData[i]->g = g;
				m_openData[i]->h = h;
				m_openData[i]->f = f;
				m_openData[i]->parentID = parentID;
				comment( node.toString().append(" received a better parent.") );
				open()[i]->setData(f);
			}
			shouldAdd = false;
		}
	}
	
	//Als $n'\not\in open$...
	if(shouldAdd){
		comment( node.toString().append(" at estimated distance ").append(QString().setNum(f)).append(" was added to open list.") );
		
		//Voeg $n'$ toe aan $open$.
		open().push_back( (new ContainerElement)->setNode(node)->setData(f) );
		m_openData.push_back( new Data( g, h, f, parentID ) );
	}
}
\end{lstlisting}
Nu is in listing~\ref{Code:AStar4} dus de \function{addToOpenList()} functie besproken. Deze verschilt echter veel van de pseudocode. De parameters $f, g$ en $h$ worden eerst berekend. Dan wordt gekeken of de betreffende knoop al in de open lijst aanwezig is. Indien dit het geval is en de huidige knoop een beter alternatief als parent, dan worden de parameters in de datastructuur gekopi\"eerd. Wordt deze knoop niet gevonden, dan wordt ze zonder veel problemen toegevoegd aan de open lijst. Voor volledigheid zal in listing~\ref{Code:AStar5} de \function{guessDistance()} functie getoond worden.

\begin{lstlisting}[label={Code:AStar5}, caption={AlgAStar.cpp: guessDistance()}]
double AlgAStar::guessDistance( const Node &node ){
	Coordinates a(node.label().toAscii().data());
	Coordinates b(m_dest->label().toAscii().data());
	return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
\end{lstlisting}
De implementatie getoond in listing~\ref{Code:AStar5} is inderdaad simpele driehoeksmeetkunde. Als men weer de code in listing~\ref{Code:AStar3} bekijkt, de \function{astar()} functie, merkt men op dat hoofdzakelijk de \function{selectFromOpenList()} functie nog ontbreekt. Deze zal getoond worden in figuur~\ref{Code:AStar6}. Zoals eerder in de pseudocode aangegeven, zal deze functie het element uit $open$ met laagste $f$ verwijderen en deze aan de $closed$ lijst toevoegen.

\begin{lstlisting}[label={Code:AStar6}, caption={AlgAStar.cpp: selectFromOpenList()}]
void AlgAStar::selectFromOpenList(){
	//Vind de knoop uit $open$ met laagste $f$ kost.
	int pos = 0;
	int minF = open()[0]->dataDouble();
	for( int i = 1; i < open().size(); i++ ){
		if( open()[i]->dataDouble() < minF ){
			minF = open()[i]->dataDouble();
			pos = i;
		}
	}
	
	//Verwijder deze uit de $open$ lijst.
	ContainerElement *e = open().takeAt(pos);
	Data *d = m_openData.takeAt(pos);
	
	comment( e->node()->toString().append(" at estimated distance ").append(QString().setNum(e->dataDouble())).append( " was selected from open list. Moved to closed list." ) );
	
	//Voeg ze toe aan de $closed$ lijst.
	closed().push_front( e );
	m_closedData.push_front( d );
}
\end{lstlisting}
Vanwege de manier waarop \function{selectFromOpenList()} werkt, wordt dus in listing~\ref{Code:AStar3} regels 13--14 het voorste element uit de $closed$ lijst gebruikt. De functies \function{isInClosedList()} en \function{otherNode()} zijn niet getoond, maar hun implementatie is zeer voordehandliggend. Tot slot wordt nog \function{printRoute()} getoond in listing~\ref{Code:AStar7}.

\begin{lstlisting}[label={Code:AStar7}, caption={AlgAStar.cpp: printRoute()}]
//Bij eerste aanroep zal $n=*m\_dest$.
void AlgAStar::printRoute( const Node &n, Data *d ){
	
	//In deze string zal dit deel van het pad komen.
	char str[1024];
	
	//Zijn we de startknoop, dan eindigt de recursie hier.
	if( d->parentID == -1 )
		sprintf(str, "Node %\%)d, %\%)s\n", n.identifier(), n.label().toAscii().data());
	else{
		//Vind de parent knoop.
		const Node %\&)parent = graph()->nodeWithId(d->parentID);
		
		//Vind de bijbehorende data.
		bool found = false;
		for( unsigned int i = 0; i < closed().size() && !found; i++ ){
			found = *closed()[i]->node() == parent;
			
			//Druk eerst het pad tot de parent af.
			if(found)
				printRoute(*closed()[i]->node(), m_closedData[i]);
		}
		sprintf(str, "Node %\%)d, %\%)s\n", n.identifier(), n.label().toAscii().data() );
	}
	
	//Nu wordt ons deel getoond en highlighten we de betreffende knoop om te tonen dat het een deel van het kortste pad is.
	comment(str);
	highlight(n);
}
\end{lstlisting}
Na listing~\ref{Code:AStar7} is alle belangrijke code besproken en kan de uitvoering van dit algoritme getoond worden.

\subsubsection{Visualizatie}\label{Text:Visualizaties:AStar:Visualizatie}
De graaf die gebruikt zal worden bij de visualizatie van het A* algoritme wordt getoond in figuur~\ref{AlgAStar:exec1}.

\ctable[pos=h!t, figure, botcap, caption={A* Algoritme}, label={AlgAStar:exec1}]{c}{}{\includegraphics[scale=.5]{images/AlgAStar/AlgAStar1.png}}

Echter, de graaf in figuur~\ref{AlgAStar:exec1} is de graaf die bedoeld werd. Dit is helaas niet in te laden in een \class{Graph}, dus zal de gebruikte voorstelling zijn zoals in figuur~\ref{AlgAStar:exec2}. Men kan opmerken dat beide grafen inderdaad gelijk zijn, buiten de plaatsing van de knopen en de toegevoegde labels.

\ctable[pos=h!t, figure, botcap, caption={A* Algoritme}, label={AlgAStar:exec2}]{c}{}{\includegraphics[scale=.35]{images/AlgAStar/AlgAStar2.png}}

Zodra het algoritme begint, wordt de bronknoop aan de open lijst toegevoegd. In deze run van het algoritme zoeken we naar het kortste pad tussen de knopen met labels $0.0$ $3.0$ en $1.0$ $1.0$. Dit wordt getoond in figuur~\ref{AlgAStar:exec3}. Merk op dat de geschatte afstand $\sqrt{ (1.0-0.0)^2 + (1.0-3.0)^2 } = \sqrt{5}$ is.

\ctable[pos=h!t, figure, botcap, caption={A* Algoritme}, label={AlgAStar:exec3}]{c}{}{\includegraphics[scale=.3]{images/AlgAStar/AlgAStar3.png}}

De bronknoop wordt verplaatst naar de gesloten lijst (container 1) en de knopen verbonden met deze komen in de open lijst (container 0). Dit is te zien in figuur~\ref{AlgAStar:exec4}.

\ctable[pos=h!t, figure, botcap, caption={A* Algoritme}, label={AlgAStar:exec4}]{c}{}{\includegraphics[scale=.3]{images/AlgAStar/AlgAStar4.png}}

Men merkt op in figuur~\ref{AlgAStar:exec4} dat de knoop die nu dichtstbij geschat wordt knoop 2 met label $0.0$ $2.0$ is. Deze zal aan de closed lijst toegevoegd worden, en dan loopt het dood. Het algoritme zal vervolgens verder gaan met knoop 1 met label $0.0$ $4.0$ en uiteindelijk in de status die getoond wordt in figuur~\ref{AlgAStar:exec5} terecht komen.

\ctable[pos=h!t, figure, botcap, caption={A* Algoritme}, label={AlgAStar:exec5}]{c}{}{\includegraphics[scale=.5]{images/AlgAStar/AlgAStar8.png}}

Ook in figuur~\ref{AlgAStar:exec5} staat het algoritme weer voor een keuze. In dit geval zal het duidelijk voor knoop 7 met label $3.0$ $3.0$ kiezen, deze ligt het dichtst bij de bestemming. De stap naar $3.0$ $2.0$ is logisch. Vervolgens zal de eindknoop in de open lijst terecht komen, naar closed verplaatst worden en dan eindigt het algoritme. Het uiteindelijke scherm waar het resulterende kortste pad getoond wordt ziet men in figuur~\ref{AlgAStar:exec6}.

\ctable[pos=h!t, figure, botcap, caption={A* Algoritme}, label={AlgAStar:exec6}]{c}{}{\includegraphics[scale=.5]{images/AlgAStar/AlgAStar11.png}}

%TEMP
\newpage
\subsection{Algoritme van Bellman-Ford}
Een tweede algoritme dat het kortste pad probleem oplost is het algoritme van Bellman-Ford. Echter, in tegenstelling tot het A* algoritme lost dit de `single source lowest cost' variant op. Dit wil zeggen dat, gegeven \'e\'en bronknoop, het de kortste paden van deze knoop naar eender welke andere knoop zal berekenen. De pseudocode voor dit algoritme is te zien in listing~\ref{Pseudo:BF}.

\begin{lstlisting}[language={}, caption={Algoritme van Bellman-Ford}, label={Pseudo:BF}]
Kies een bronknoop $n_0$.
Voor een knoop $n$ %defini\"eer) $n.distance$ en $n.parent$.
Voor alle knopen $n\in G$...
	Als $n==n_0$ dan $n.distance = 0$.
	Anders $n.distance=\infty$.
	n.parent = null.
Herhaal $G->numNodes$ maal...
	Voor iedere boog $uv\in G$...
		$u=uv.from$.
		$v=uv.to$.
		Als $u.distance+uv.weight<v.distance$...
			$v.distance=u.distance+uv.weight$.
			$v.parent = u$
\end{lstlisting}

\subsubsection{Implementatie}
De pseudocode getoond in listing~\ref{Pseudo:BF} is zeer gemakkelijk te implementeren. Het bijhouden van $n.distance$ en $n.parent$ doen we door gebruik te maken van een container. Aan het begin van het algoritme zullen alle knopen aan \'e\'en container toegevoegd worden. De distance zal als double aan de container toegevoegd worden, de parent zal als boog toegevoegd worden. In de pseudocode werd een knoop zelf as parent gebruikt, echter, door een edge te gebruiken ziet de visualizatie er beter uit en is het niet nodig om aparte datastructuren te gebruiken.

In listing~\ref{Code:AlgBF1} ziet men de \function{run()} functie voor dit algoritme. Merk op dat in de constructor \'e\'en container toegevoegd is en de \function{c()} functie geeft een referentie naar deze terug.

\begin{lstlisting}[caption={AlgBellmanFord.cpp: run}, label={Code:AlgBF1}]
void AlgBellmanFord::run(){
	//Kies een bronknoop $n$.
	Node *n = getNode("Please select the source Node");
	
	Voor alle knopen $node\in G$...
	for( unsigned int i = 0; i < graph()->numNodes(); i++ ){
		const Node &node = graph()->node(i);
		
		//Als $n==n_0$ dan $n.distance = 0$.
		//Anders $n.distance=\infty$.
		//n.parent = null.
		c().push_back( (new ContainerElement)->setNode(node)->setData(node==*n?0.0:INF) );
	}
	
	//Herhaal $G->numNodes$ maal...
	for( unsigned int i = 0; i < graph()->numNodes(); i++ ){
	
		//Voor iedere boog $uv\in G$...
		for( unsigned int j = 0; j < graph()->numEdges(); j++ ){
			const Edge &uv = graph()->edge(j);
			
			//$u=uv.from$.
			const Node &u = uv.from();
			
			//$v=uv.to$.
			const Node &v = uv.to();
			
			//Als $u.distance+uv.weight<v.distance$...
			double total = distance(u)+weight(uv);
			if( total < distance(v) ){
			
				//$v.distance=u.distance+uv.weight$.
				//$v.parent = uv$
				setData(v, total, uv );
				
				//Herhalen in omgekeerde richting als $G$ ongericht.
				if(!graph()->isDirected()){
				total = distance(v)+weight(uv);
				if( total < distance(u) )
					setData(u, total, uv);
			}
			}
		}
	}
	delete n;
}
\end{lstlisting}
Men merkt op dat de \function{run()} functie in listing~\ref{Code:AlgBF1} zeer sterk op de pseudocode lijkt. Dit feit is grotendeels te danken aan het gebruik van functies zoals \function{distance()} en \function{weight()}, met elk een zeer voordehandliggende implementatie. \function{setData()} is echter nogal abstract op dit moment en wordt getoond in listing~\ref{Code:AlgBF2}.

\begin{lstlisting}[caption={AlgBellmanFord.cpp: setData()}, label={Code:AlgBF2}]
void AlgBellmanFord::setData( const Node &n, double d, const Edge &e ){
	//Zoek het ContainerElement dat knoop $n$ bevat...
	for( unsigned int i = 0; i < c().size(); i++ ){
		if( *c()[i]->node() == n ){
			//Zet de afstand van $n$ op $d$ en haar parent op $e$.
			c()[i]->setData(d)->setEdge(e);
			return;
		}
	}
}
\end{lstlisting}

Ook de code in listing~\ref{Code:AlgBF2} is zeer voordehandliggend. Tot slot worden \function{distance()} en \function{weight()} nog getoond in listing~\ref{Code:AlgBF3}.

\begin{lstlisting}[label={Code:AlgBF3}, caption={AlgBellmanFord.cpp: distance() en weight()}]
double AlgBellmanFord::distance(const Node &n){
	for( unsigned int i = 0; i < c().size(); i++ ){
		if( *c()[i]->node() == n )
			return c()[i]->dataDouble();
	}
	return INF;
}

double AlgBellmanFord::weight(const Edge &e){
	return e.label().remove("\"").toDouble();
}
\end{lstlisting}
Ook deze code was zeer eenvoudig, maar toch heeft ze duidelijk bijgedragen aan het leesbaarder maken van de \function{run()} functie.

\subsubsection{Visualizatie}
Aan het begin van de uitvoering van dit algoritme worden we gevraagd een bronknoop te selecteren. Dit ziet men in figuur~\ref{AlgBF:exec1}. Knoop $A$ wordt gekozen.

\ctable[pos=h!t, figure, botcap, caption={Algoritme van Bellman-Ford}, label={AlgBF:exec1}]{c}{}{\includegraphics[scale=.35]{images/AlgBellmanFord/AlgBellmanFord1.png}}

%TEMP
\newpage
Nu de bronknoop gekozen werd, kunnen alle knopen aan de gebruikte container toegevoegd worden, met hun kost ge\"initialiseerd. Dit ziet men in figuur~\ref{AlgBF:exec2}.

\ctable[pos=h!t, figure, botcap, caption={Algoritme van Bellman-Ford}, label={AlgBF:exec2}]{c}{}{\includegraphics[scale=.35]{images/AlgBellmanFord/AlgBellmanFord2.png}}

In figuur~\ref{AlgBF:exec3} ziet men dat een pad naar knoop $B$ gevonden is.

\ctable[pos=h!t, figure, botcap, caption={Algoritme van Bellman-Ford}, label={AlgBF:exec3}]{c}{}{\includegraphics[scale=.35]{images/AlgBellmanFord/AlgBellmanFord3.png}}

%TEMP
\newpage
In figuur~\ref{AlgBF:exec4} is een pad naar $D$ gevonden.

\ctable[pos=h!t, figure, botcap, caption={Algoritme van Bellman-Ford}, label={AlgBF:exec4}]{c}{}{\includegraphics[scale=.35]{images/AlgBellmanFord/AlgBellmanFord4.png}}

Tot slot laat figuur~\ref{AlgBF:exec5} het uiteindelijke resultaat zien. De paden die gemarkeerd zijn, zijn de paden via welke alle knopen met de kortste route te bereiken zijn. Logischerwijs is als resultaat eerder een boom ontstaan, die toevallig\footnote{Gezien beide bogen vertrekkende uit $A$ ook in de MST voor deze graaf zitten is dit niet toevallig.} volledig overeenkomt met de MST van deze graaf, zoals gezien in de vorige secties.

\ctable[pos=h!t, figure, botcap, caption={Algoritme van Bellman-Ford}, label={AlgBF:exec5}]{c}{}{\includegraphics[scale=.35]{images/AlgBellmanFord/AlgBellmanFord6.png}}

\subsection{Algoritme van Dijkstra}
Het algoritme van Dijkstra werkt gelijkaardig aan het algoritme van Bellman-Ford en lost ook het `single source shortest path' probleem op\cite{cursus}. De pseudo-code voor dit probleem wordt getoond in listing~\ref{Pseudo:Dijkstra}.

\begin{lstlisting}[language={}, caption={Dijkstra's Algoritme}, label={Pseudo:Dijkstra}]
Noem $G$ de graaf.
Neem $D$ een afstandsvector.
Neem $P$ een padvector.
Neem $S$ als verzameling van alle knopen.
Neem knoop $0$ als bronknoop.

Initialiseer alle elementen van $P$ op $0$ (de bronknoop).
Initialiseer alle elementen van $S$ op $false$. Zet $S[0]$ op $true$.

Voor alle knopen $k\in G$ doe...
	D[k] = G[0][k].

Voor $i$ van $1$ tot $n$, doe...
	Neem $w$ de knoop op minimale afstand van knoop $0$ waar $S[w] = false$.
	$S[w] = true$.
	
	Voor alle knopen $v$ in $G$, doe...
		Als (!S[v]) && D[v] > D[w] + G[w][v]..
			D[v] = D[w] + G[w][v].
			P[v] = w.

D bevat nu de afstand van de bronknoop naar alle andere knopen.
P bevat nu de paden genomen van de bronknoop naar alle andere knopen.
\end{lstlisting}

\subsubsection{Implementatie}
Om dit algoritme te implementeren zal \'e\'en container gebruikt worden. Deze container zal een knoop bevatten, de knoop waarover het verdere informatie bevat, een integer die ofwel 0 of 1 is om $S$ te implementeren, een double om $D$ te implementeren, en een boog om $P$ te implementeren. Als we deze veranderingen doorvoeren in pseudocode, komen we uit op de code in listing~\ref{Pseudo:Dijkstra2}.

\begin{lstlisting}[language={}, caption={Dijkstra's Algoritme}, label={Pseudo:Dijkstra2}]
Noem $G$ de graaf.
Neem $c$ een container.
Kies een knoop $n_0$ als bronknoop.

Voor alle knopen $n\in G$...
	Voeg $n$ toe aan $c$.
	Zet $c[n]->int$ op 0.
	Zet $c[n]->double$ op $\infty$.
Zet $c[n_0]->int$ op 0.
Zet $c[n_0]->double$ op $0.0$.

Voor alle paden $e$ vanuit $n_0$...
	Als $cost(e) < c[e.to]->int$...
		$c[e.to]->double = cost(e)$.
		$c[e.to]->edge = e$.
		
Voor $i$ van $1$ tot $G->numNodes$ doe...
	Neem $w$ de knoop op minimale afstand van $n_0$ waar $c[w]->int == 0$.
	Zet $c[w]->int$ op 1.
	Voor alle knopen $v\in G$ doe...
		Als $c[v]->int == 1$, sla deze stap over.
		Als $c[v]->double > c[w]->double + cost(G[w][v])$...
			$c[v]->double = c[w]->double + cost(G[w][v])$.
			$c[v]->edge = G[w][v]$.
Container $c$ bevat nu alle knopen en de kost benodigd om deze te bereiken.
\end{lstlisting}

Nu kan de pseudocode in listing~\ref{Pseudo:Dijkstra2} gemakkelijk omgezet worden in een werkelijk algoritme. Dit wordt getoond in listing~\ref{Code:Dijkstra}. Enkel de \function{run()}  functie wordt hier getoond. Functies om deze te ondersteunen worden later verklaard. Merk alvorens de code te bekijken op dat in de constructor \'e\'en aanroep naar \function{containerAdd()} is gedaan.

\begin{lstlisting}[label={Code:Dijkstra}, caption={AlgDijkstra.cpp: run}]
void AlgDijkstra::run(){
	//Kies een knoop $source$ als bronknoop.
	Node *source = getNode("Please select the source Node");
	
	//Voor alle knopen $n\in G$...
	for( unsigned int i = 0; i < graph()->numNodes(); i++ ){
		const Node &n = graph()->node(i);
		
		//Voeg $n$ toe aan $c$.
		//Zet $c[n]->int$ op 0.
		//Zet $c[n]->double$ op $\infty$.
		bool isSource = n == *source;
		c().push_back( (new ContainerElement)->setNode(n)->setData(isSource?0.0:INF)->setData(isSource?1:0) );
	}
	
	//Zet $c[source]->int$ op 0.
	//Zet $c[source]->double$ op $0.0$.
	//Merk op dat dit in de vorige stap al gedaan is.
	
	//Voor alle paden $e$ vanuit $source$...
	QList<Edge> edgesFromSource = graph()->edgesFrom(*source);
	for( int i = 0; i < edgesFromSource.size(); i++ ){
		const Edge &e = edgesFromSource[i];
		const Node &n = otherNode(e, *source);
		double cost = e.label().toDouble();
		
		Als $cost(e) < c[e.to]->int$...
		if( cost < distance( n ) ){
		
			//$c[e.to]->double = cost(e)$.
			//$c[e.to]->edge = e$.
			setDistance( n, cost, e );
		}
	}
	
	//Voor $i$ van $1$ tot $G->numNodes$ doe...
	for( unsigned int i = 1; i < graph()->numNodes(); i++ ){
		
		//Neem $w$ de knoop op minimale afstand van $n_0$ waar $c[w]->int == 0$.
		//Zet $c[w]->int$ op 1.
		const Node *nodeW = minUnseenNode();
		if(nodeW==0)
			return;
		
		//Voor alle knopen $v\in G$ doe...
		for( unsigned int j = 0; j < c().size(); j++ ){
			//Als $c[v]->int == 1$, sla deze stap over.
			if( c()[j]->dataInt() == 1 )
				continue;
			const Node *nodeV = c()[j]->node();
			
			//Sla deze stap over indien deze twee knopen niet direct door een boog verbonden zijn.
			int edgeID = (*graph())[nodeW->identifier()][nodeV->identifier()];
			if( edgeID < 0 )
				continue;
			
			const Edge &edge = graph()->edgeWithId(edgeID);
			double cost = distance(*nodeW) + edge.label().toDouble();
			
			//Als $c[v]->double > c[w]->double + cost(G[w][v])$...
			if( cost < distance(*nodeV) ){
			
				//$c[v]->double = c[w]->double + cost(G[w][v])$.
				//$c[v]->edge = G[w][v]$.
				setDistance(*nodeV, cost, edge);
			}
		}
	}
}
\end{lstlisting}

Nu was de code in listing~\ref{Code:Dijkstra} een vrij letterlijke vertaling van de pseudo-code. Er waren echter enkele functies gebruikt die in de betreffende listing niet getoond werden. De functie \function{otherNode()} is toegevoegd om ook met ongerichte grafen te kunnen werken, en zal verder niet uitgelegd worden. \function{distance()} en \function{setDistance()} worden hieronder getoond in listing~\ref{Code:Dijkstra2}.

\begin{lstlisting}[caption={AlgDijkstra.cpp: distance() en setDistance()}, label={Code:Dijkstra2}]
double AlgDijkstra::distance( const Node &n ){
	for( unsigned int i = 0; i < c().size(); i++ ){
		if( n == *c()[i]->node() )
			return c()[i]->dataDouble();
	}
	return INF;
}

void AlgDijkstra::setDistance( const Node &n, double d, const Edge &parent ){
	for( unsigned int i = 0; i < c().size(); i++ ){
		if( n == *c()[i]->node() ){
			c()[i]->setData(d)->setEdge(parent);
			break;
		}
	}
}
\end{lstlisting}

Beide functies getoond in listing~\ref{Code:Dijkstra2} zijn zeer recht-toe-recht-aan. Er wordt gezocht naar het ContainerElement dat de betreffende knoop bevat en ofwel wordt het double element gereturnd, ofwel wordt de bijgehouden data aangepast. Tot slot ontbreekt enkel de \function{minUnseenNode()} functie nog. Deze wordt getoond in listing~\ref{Code:Dijkstra3}.

\begin{lstlisting}[caption={AlgDijkstra.cpp: minUnseenNode()}, label={Code:Dijkstra3}]
const Node *AlgDijkstra::minUnseenNode(){
	double minCost = INF;
	int minI = -1;
	for( unsigned int i = 0; i < c().size(); i++ ){
		if( c()[i]->dataInt() == 0 ){
			if( c()[i]->dataDouble() < minCost ){
				minCost = c()[i]->dataDouble();
				minI = i;
			}
		}
	}
	if( minI == -1 )
		return 0;
	
	c()[minI]->setData(1);
	return c()[minI]->node();
}
\end{lstlisting}

Ook de code in listing~\ref{Code:Dijkstra3} is relatief voordehandliggend. Er wordt verondersteld dat geen knoop gevonden wordt, wordt deze toch gevonden, dan wordt haar afstand en nummer in de lijst bijgehouden. Is deze uiteindelijk van laagste kost, dan wordt zij gereturnd. Merk nogmaals op dat \function{ContainerElement::dataInt()} gebruikt wordt om $S$ uit de pseudo-code voor te stellen.

\subsubsection{Visualizatie}

Visualizatie van het algoritme van Dijkstra zal dan gaan als volgt. 

%TEMP
\newpage
\ctable[pos=h!t, figure, botcap, caption={Dijkstra's Algoritme}, label={AlgDijkstra:exec0}]{c}{}{\includegraphics[scale=.4]{images/AlgDijkstra/AlgDijkstra1.png}}

De gebruikte graaf en de selectie van de startknoop (knoop $A$) worden getoond in figuur~\ref{AlgDijkstra:exec0}.

\ctable[pos=h!t, figure, botcap, caption={Dijkstra's Algoritme}, label={AlgDijkstra:exec1}]{c}{}{\includegraphics[scale=.4]{images/AlgDijkstra/AlgDijkstra2.png}}

Figuur~\ref{AlgDijkstra:exec1} toont de beginsituatie. Container $c$ is hier pas net ge\"initialiseerd.

%TEMP
\newpage
\ctable[pos=h!t, figure, botcap, caption={Dijkstra's Algoritme}, label={AlgDijkstra:exec2}]{c}{}{\includegraphics[scale=.4]{images/AlgDijkstra/AlgDijkstra3.png}}

In een verder stadium van initialisatie zijn we in figuur~\ref{AlgDijkstra:exec2}. De paden vanuit de bron worden nu doorlopen. Het pad $0\rightarrow 1$ wordt hier gevonden. Gezien $7 < 999$, wordt dit toegevoegd.

\ctable[pos=h!t, figure, botcap, caption={Dijkstra's Algoritme}, label={AlgDijkstra:exec3}]{c}{}{\includegraphics[scale=.4]{images/AlgDijkstra/AlgDijkstra4.png}}

Figuur~\ref{AlgDijkstra:exec3} toont ons de situatie na de volledige initialisatie. Beide bogen vanuit de bron zijn nu toegevoegd.

%TEMP
\newpage
\ctable[pos=h!t, figure, botcap, caption={Dijkstra's Algoritme}, label={AlgDijkstra:exec4}]{c}{}{\includegraphics[scale=.4]{images/AlgDijkstra/AlgDijkstra5.png}}

Figuur~\ref{AlgDijkstra:exec4} toont ons dat de $min$ functie hier knoop $3$ teruggaf. Deze knoop had als integer data $1$ (enkel $0$ had $0$ op dit moment), en het dichtst bij de bron: $5 < 7$. Vandaar dat in deze stap $3\rightarrow 4$ toegevoegd wordt aan $c[4]$, dit is het kortste bekende pad waardoor deze knoop bereikt kan worden. Merk op dat $0\rightarrow 1\rightarrow 4$ korter is. Knoop $1$ is echter nog niet als $w$ knoop beschouwd.

\ctable[pos=h!t, figure, botcap, caption={Dijkstra's Algoritme}, label={AlgDijkstra:exec5}]{c}{}{\includegraphics[scale=.4]{images/AlgDijkstra/AlgDijkstra6.png}}

Figuur~\ref{AlgDijkstra:exec5} toont ons de situatie na afloop van het algoritme. Duidelijk is dat het eerder geselecteerde pad $3\rightarrow 4$ nu niet meer gebruikt wordt. Op de weergegeven graaf zelf wordt netjes getoond dat er vanuit iedere knoop slechts \'e\'en gemarkeerd (kortst) pad vanaf de bron is.


\subsection{Algoritme van Floyd}
Dit algoritme lost de laatste variant van het padenprobleem op. Gegeven een graaf. Zoek alle kortste paden tussen elk paar van twee knopen, indien dit bestaat.\cite[p.~217]{cursus}

Het algoritme dat dit probleem oplost kan beschreven worden als volgt.

\begin{lstlisting}[language={}, caption={Floyd's algoritme}, label={Alg:Floyd}]
Gegeven graaf $G$.
Noem $T$ de resultaatgraaf.
Noem $P$ een graaf die de gebruikte paden bijhoudt.

Initialiseer $T$ als $G$.
Initialiseer $P$ met alle elementen $-1$.

Voor alle knopen $k\in T$...
	Voor alle knopen $v\in T$...
		Voor alle knopen $w\in T$...
			Indien kost($v\rightarrow k$ + $k\rightarrow w$) goedkoper dan kost($v\rightarrow w$)...
				T[v][w] = T[v][k] + T[k][w]
				P[v][w] = k
				
\end{lstlisting}


\subsubsection{Implementatie}
Om de visualizatie zo eenvoudig mogelijk te houden wordt de pad-graaf $P$ buiten beschouwing gelaten. Zoals bij het algoritme van Warshall gebruiken we de huidige graaf om $T$ te representeren. Dit kan geen kwaad, gezien de graaf $G$ in het algoritme enkel gebruikt wordt om $T$ te initialiseren.

Omdat de implementatie van een graaf zo algemeen mogelijk is gehouden, is het mogelijk dat er meerdere bogen tussen twee dezelfde knopen zijn. In het begin van het algoritme moeten deze dus verwijderd worden. Dit wordt gedaan door de code in listing~\ref{Code:Floyd1}. Dit is geen werkelijk deel van het bovenstaand beschreven algoritme, omdat dit algoritme het bestaan van dergelijke bogen vermijdt.

\begin{lstlisting}[caption={Floyd's Algoritme: Constructor}, label={Code:Floyd1}]
AlgFloyd::AlgFloyd( Graph *g ): Algorithm( g ){
	
	//Voor alle knopen $i\in g$...
	for( int i = 0; i < g->numNodes(); i++ ){
	
		//Voor alle bogen $j$ die in $i$ starten...
		QList<Edge> edges = g->edgesFrom( g->node(i) );
		for( int j = 0; j < edges.size(); j++ ){
			
			//Voor alle bogen $k$ die na $j$ in $i$ starten...
			for( int k = j+1; k < edges.size() && j >= 0; k++ ){
			
				//Indien dit een gerichte graaf is en beide bogen in dezelfde knoop aankomen
				if( g->isDirected() && edges[j].to() == edges[k].to() ){
				
					//Verwijder de duurste boog.
					if( edges[j].label().toInt() > edges[k].label().toInt() ){
						g->removeEdge(edges[j]);
						edges.takeAt(j);
						j--;
					}else{
						g->removeEdge(edges[k]);
						edges.takeAt(k);
						k--;
					}
				
				//Indien dit een ongerichte graaf is...
				}else if( !g->isDirected() ){
					int removeThis = -1;
					if( edges[j].from() == edges[k].from() && edges[j].to() == edges[k].to() ){
						removeThis = edges[j].label().toInt() > edges[k].label().toInt() ? j : k;
					}else if( edges[j].from() == edges[k].to() && edges[j].to() == edges[k].from() ){
						removeThis = edges[j].label().toInt() > edges[k].label().toInt() ? j : k;
					}
					
					//Indien beide bogen tussen dezelfde twee knopen zijn, verwijder de duurste.
					if( removeThis >= 0 ){
						g->removeEdge(edges[removeThis]);
						edges.takeAt(removeThis);
						if( removeThis == j )
							j--;
						else
							k--;
					}
				}
						
			}
		}
	}
}

\end{lstlisting}

Nu het geval van meerdere bogen tussen dezelfde twee knopen vermeden is, kan het algoritme relatief simpel geimplementeerd worden. Voor het gemak zal weer de pseudocode in het commentaar meegeleverd worden.

\begin{lstlisting}[caption={Implementatie Floyd's Algoritme}, label={Code:Floyd2}]
void AlgFloyd::run(){
	int n = graph()->numNodes();
	
	//Voor alle nodes $k$...
	for( int k = 0; k < n; k++ ){
	
		//Voor alle nodes $v$...
		for( int v = 0; v < n; v++ ){
		
			//Voor alle nodes $w$...
			for( int w = 0; w < n; w++ ){
			
				//Bereken de kosten
				const Edge *p;
				int costvk = cost(v,k);
				int costkw = cost(k,w);
				int costvw = cost(v,w, &p);
				
				//Indien kost($v\rightarrow k$ + $k\rightarrow w$) goedkoper dan kost($v\rightarrow w$)...
				if( costvk + costkw < costvw ){
				
					//Als er al een eerder pad bestond: verwijder dit.
					if( costvw < INFINITY )
						graph()->removeEdge( *p );
					
					//Als er geen werkelijk pad bestond, ga verder.
					if( costvk+costkw >= INFINITY )
						continue;
						
					//Voeg het pad met nieuwe kost toe aan de graaf.
					const Edge &e = graph()->createEdge( graph()->node(v), graph()->node(w), QString().setNum(costvk+costkw) );
					highlight(e);
				}
			}
		}
	}
}

//Bereken de kost van een pad $i\rightarrow j$ en geef eventueel het pad terug.
int AlgFloyd::cost( int i, int j, const Edge **e ){
	
	//Een pad $i\rightarrow i$ is gratis.
	if( i == j )
		return 0;
		
	//Indien er geen pad bestaat is de kost oneindig.
	int edgeID = (*graph())[i][j];
	if( edgeID < 0 )
		return INFINITY;
	
	const Edge &edge = graph()->edgeWithId(edgeID);
	if( e != 0 )
		*e = &edge;
	
	//Indien er een pad bestaat geven we haar kost terug.
	return edge.label().toInt();
}

\end{lstlisting}

\subsubsection{Visualizatie}
Visualizatie van het verloop van dit algoritme zal dan gaan als volgt.

\ctable[pos=h!t, figure, botcap, caption={Floyd's Algoritme}, label={AlgFloyd:exec2}]{c}{}{\includegraphics[scale=.5]{images/AlgFloyd/AlgFloyd2.png}}

%TEMP
\newpage
Figuur~\ref{AlgFloyd:exec2} toont de startgraaf. Men kan hier meteen opmerken dat er al 25 queries op de edges zijn gedaan. Dit is vanwege de eerder besproken constructor.

\ctable[pos=h!t, figure, botcap, caption={Floyd's Algoritme}, label={AlgFloyd:exec3}]{c}{}{\includegraphics[scale=.5]{images/AlgFloyd/AlgFloyd3.png}}

In figuur~\ref{AlgFloyd:exec3} merken we duidelijk op dat er \'e\'en nieuw pad toegevoegd is. Dit stelt het pad $5\rightarrow 2\rightarrow 3$ voor.

%TEMP
\newpage
\ctable[pos=h!t, figure, botcap, caption={Floyd's Algoritme}, label={AlgFloyd:exec4}]{c}{}{\includegraphics[scale=.5]{images/AlgFloyd/AlgFloyd4.png}}

In figuur~\ref{AlgFloyd:exec4} merken we op dat er precies \'e\'en iteratie later vijfmaal een edge gequeried is en tweemaal een knoop. Uit bovenstaande code is duidelijk dat er per iteratie ten minste 3 edges gequeried worden voor de kost. Indien een pad $i\rightarrow j$ bestaat zal de operatoe $cost( i, j )$ tweemaal naar een edge queryen. Eenmaals om het ID te achterhalen, andermaals om aan de edge zelf te komen.

\ctable[pos=h!t, figure, botcap, caption={Floyd's Algoritme}, label={AlgFloyd:exec5}]{c}{}{\includegraphics[scale=.5]{images/AlgFloyd/AlgFloyd5.png}}

In figuur~\ref{AlgFloyd:exec5} merkt men op dat er een pad uit de originele graaf verwijderd werd en een nieuwe toegevoegd. Het nieuwe pad $2\rightarrow 3\rightarrow 4$ in plaats van $2 \rightarrow 4$ is goedkoper gevonden.

\ctable[pos=h!t, figure, botcap, caption={Floyd's Algoritme}, label={AlgFloyd:exec6}]{c}{}{\includegraphics[scale=.5]{images/AlgFloyd/AlgFloyd6.png}}

Tot slot toont figuur~\ref{AlgFloyd:exec4} de eindsituatie.

%TEMP
% \clearpage
\subsection{Algoritme van Warshall}
Het probleem dat dit algoritme oplost is gelijkaardig aan het probleem centraal aan deze sectie, maar niet gelijk. Het kan verwoord worden als volgt. Gegeven een gerichte graaf. Vind de transitieve sluiting van deze graaf. De transitieve sluiting van een graaf bevat een boog tussen twee knopen, telkens als er in de originele graaf een pad tussen de twee knopen is.\cite[p.~219]{cursus}

Het algoritme dat dit probleem oplost kan beschreven worden als volgt:

\begin{lstlisting}[language={}, caption={Warshall's Algoritme}, label={Pseudo:Warshall}]
Noem de graaf $G$.
Noem $T$ haar transitieve sluiting.
Initialiseer $T$ als $G$.

Voor alle knopen $k$ in $G$...
	Voor alle knopen $v$ in $G$...
		Voor alle knopen $w$ in $G$...
			Indien $T$ geen pad $v\rightarrow w$ bevat...
				Indien $v\rightarrow k$ en $k\rightarrow w$ in $T$ bestaan
					Voeg $v\rightarrow w$ toe aan $T$.
$T$ bevat nu de transitieve sluiting van $G$.
\end{lstlisting}

\subsubsection{Implementatie}
In de plaats van een aparte graaf te gebruiken voor de transitieve sluiting, zal direct op de graaf zelf gewerkt worden. Dit heeft geen invloed op het daadwerkelijke algoritme. Voor de implementatie is geen \class{Container} benodigd. De implementatie voor dit algoritme wordt getoond in listing~\ref{Code:Warshall}. Ook hier is grotendeels de pseudocode van listing~\ref{Pseudo:Warshall} toegevoegd als commentaar voor de duidelijkheid.

\begin{lstlisting}[label={Code:Warshall}, caption={Implementatie Warshall's Algoritme}]
AlgWarshall::AlgWarshall( Graph *g ): Algorithm( g ){
	
}

AlgWarshall::~AlgWarshall(){
	
}

void AlgWarshall::run(){
	
	//Voor alle nodes $k$...
	for( int k = 0; k < graph()->numNodes(); k++ ){
	
		//Voor alle nodes $v$...
		for( int v = 0; v < graph()->numNodes(); v++ ){
		
			//Voor alle nodes $w$...
			for( int w = 0; w < graph()->numNodes(); w++ ){
				
				//Indien $v\rightarrow w$ niet bestaat.
				if( (*graph())[v][w] < 0 ){
				
					//Als $v\rightarrow k$ en $k\rightarrow w$ bestaan
					if( (*graph())[v][k] >= 0 && (*graph())[k][w] >= 0 ){
					
						//Voeg $v\rightarrow w$ toe aan de graaf.
						graph()->createEdge(graph()->node(v), graph()->node(w));
						highlight( graph()->edge(graph()->numEdges()-1) );
					}
				}
			}
		}
	}
}
\end{lstlisting}

\subsubsection{Visualizatie}
Visualizatie van het verloop van dit algoritme zal dan gaan als volgt.

%TEMP
\newpage
\ctable[pos=h!t, figure, botcap, caption={Warshall's Algoritme}, label={AlgWarshall:exec1}]{c}{}{\includegraphics[scale=.5]{images/AlgWarshall/AlgWarshall1.png}}

In figuur~\ref{AlgWarshall:exec1} ziet men de begingraaf voor dit algoritme.

\ctable[pos=h!t, figure, botcap, caption={Warshall's Algoritme}, label={AlgWarshall:exec2}]{c}{}{\includegraphics[scale=.5]{images/AlgWarshall/AlgWarshall2.png}}

In figuur~\ref{AlgWarshall:exec2} ziet men de eerste toegevoegde boog. Men merkt op dat er op dit moment al 201 edges gequeried zijn. Voor het eerst gevonden pad geldt: $k =  2, v = 5, w = 3$. Elke iteratie worden er tenminste 1, ten hoogste 4 edges gequeried, zoals in het algoritme te zien. Het is dus te verwachten dat dit aantal inderdaad zeer sterk stijgen zal.

%TEMP
\newpage
\ctable[pos=h!t, figure, botcap, caption={Warshall's Algoritme}, label={AlgWarshall:exec3}]{c}{}{\includegraphics[scale=.5]{images/AlgWarshall/AlgWarshall3.png}}

In figuur~\ref{AlgWarshall:exec3} ziet men de tweede toegevoegde boog. Op dit moment zijn er 205 edges gequeried. Dit is niet veel meer dan in figuur~\ref{AlgWarshall:exec2}. Men kan opmerken dat geldt: $k =  2, v = 5, w = 4$.

\ctable[pos=h!t, figure, botcap, caption={Warshall's Algoritme}, label={AlgWarshall:exec4}]{c}{}{\includegraphics[scale=.5]{images/AlgWarshall/AlgWarshall4.png}}

Figuur~\ref{AlgWarshall:exec4} toont de eindsituatie van dit algoritme, de transitieve sluiting van de startgraaf. Alle toegevoegde paden zijn hier rood gemarkeerd.

\chapter{Conclusie}\label{Text:Programma}\label{Text:Conclusie}
Nu in dit document het volledige thesisproject, het programma en de meegeleverde algoritmes besproken zijn, is het tijd om terug te kijken naar de doelstellingen die in hoofdstuk~\ref{Text:Doelstellingen} opgesteld werden en deze te evalueren. Ook zullen enkele tekortkomingen in dit hoofdstuk besproken worden.

\section{Doelstellingen}
Eerst zullen de doelstellingen uit hoofdstuk~\ref{Text:Doelstellingen} hier kort herhaald worden.
\begin{enumerate}
\item Elk mogelijk type graaf voorstellen.
\item Een zo bruikbaar, maar nog steeds algemeen mogelijke interface bieden voor het werken met grafen.
\item Wijzigingen in de structuur van de graaf kunnen weergeven. (Zie de laatste afbeeldingen in figuur~\ref{AlgKruskal:Exec}, dergelijke wijzigingen willen we kunnen zien).
\item Een zo algemeen mogelijk lijst-type aanbieden dat de gebruiker kan benutten om informatie in op te slaan. Dit zal gebruikt moeten kunnen worden om bijvoorbeeld knopen, bogen, getallen, etc op te kunnen slaan. Het programma zal het gebruik hiervan kunnen benutten om informatie over het algoritme te winnen.
\item Aan de gebruiker toelaten tijdens de voortgang van het algoritme een specifieke knoop of boog manueel te markeren om op deze manier informatie over het algoritme te communiceren. Indien de eerste vier doelstellingen niet genoeg zijn om het verloop van een algoritme degelijk te tonen, kan op z'n minst de gebruiker hier zelf nog enigszins aan sleutelen.
\item Bijhouden hoeveel de gebruikte structuren gequeried worden, zodat de gebruiker een beeld krijgt van de complexiteit van het algoritme.
\item Aan de gebruiker toelaten tijdens de uitvoering van zijn zelfgeschreven algoritme commentaar te geven op de gevolgde stappen en dit weer te geven.
\end{enumerate}

\subparagraph{Elk mogelijk type graaf voorstellen.}
Gezien er geen restrictie is gezet op het aantal bogen dat twee verschillende knopen mag verbinden en een graaf zowel gericht of ongericht kan zijn is hier aan voldaan. Echter, neem een boog $e$ en een knoop $n$. Het scenario in listing~\ref{Doelstellingen:1} is dan zeer mogelijk.

\begin{lstlisting}[caption={Probleem met ongerichte graaf}, label={Doelstellingen:1}]
const Node &n = graph()->node(0);
QList<Edge> edges = graph()->edgesFrom(n);
for( unsigned int i = 0; i < edges.size(); i++ ){
	if( edges[i].from() != n )
		printf( "%\%)s does not start from %\%)s!\n", edges[i].toString().toAscii().value(), n.toString().toAscii().value() );
}
\end{lstlisting}

Om dit te voorkomen moet men in algoritmen die ongerichte grafen accepteren, er voor zorgen dat het altijd zowel \function{Edge::from()} als \function{Edge::to()} beschouwt.

\subparagraph{Een zo bruikbaar, maar nog steeds algemeen mogelijke interface bieden voor het werken met grafen.}
Het type graaf is inderdaad zeer algemeen gebleven. Bruikbaar is het zeker ook te noemen, dus grotendeels is aan deze doelstelling voorzien. Er zijn echter wel soms wat onhandigheidjes met de interface.

Het gebruik van unieke identifiers voor knopen en bogen is grotendeels een noodzakelijk kwaad. In het geval van iteratie over alle knopen/bogen van een graaf, echter, wordt deze identifier niet gebruikt en wordt simpelweg het `volgnummer' van deze structuur gebruikt. Zo geeft een aanroep \function{graph()->node(0)} niet altijd hetzelfde resultaat als een aanroep \function{graph()->nodeWithId(0)}. Dit is verwarrend en hier had best omheengewerkt geweest.

Ook zijn de datastructuren helaas niet uitbreidbaar. Een boog, bijvoorbeeld, heeft als membervariabelen een label, een identifier en twee knopen. Indien men deze boog een kost wil geven, dan kan dat, maar moet deze kost in het label opgeslagen worden. Als men dan echter de boog ook een naam wilt geven, dan heeft men een probleem. Beide zouden dan in het label opgeslagen moeten worden, wat ongewenst is indien men wilt dat enkel de naam getoond wordt.

Tot slot wil ik nog verwijzen naar hoofdstuk~\ref{Text:Visualizaties:AStar:Visualizatie}. Hier wordt getoond dat de weergave van een graaf helaas op zich niet flexibel is.

\subparagraph{Wijzigingen in de structuur van de graaf kunnen weergeven.} Wijzigingen in de structuur van een graaf worden altijd weergegeven. Hier is dus zeker aan voldaan. Echter, na een wijziging in de structuur kan de graaf soms een onverwachte vorm aannemen.

\subparagraph{Een zo algemeen mogelijk lijst-type aanbieden dat de gebruiker kan benutten om informatie in op te slaan.}
Hier is grotendeels aan voldaan. Echter, zoals met de graaf, is dit type niet uitbreidbaar zonder zeer veel veranderingen in het project te moeten aanbrengen (in de veronderstelling dat de aangepaste data ook getoond zou moeten worden).

\subparagraph{Aan de gebruiker toelaten tijdens de voortgang van het algoritme een specifieke knoop of boog manueel te markeren om op deze manier informatie over het algoritme te communiceren.}
Hier is aan voldaan.

\subparagraph{Bijhouden hoeveel de gebruikte structuren gequeried worden, zodat de gebruiker een beeld krijgt van de complexiteit van het algoritme.}
Hier is aan voldaan. Het is echter wel aan de gebruiker om zowel op een slimme als een eerlijke manier hiermee om te gaan. Dit wil zeggen dat van de gebruiker niet verwacht wordt een volledige kopie van de graaf te maken en hier de berekeningen op te doen, maar dat wel verwacht wordt een graaf geen tweemaal direct na elkaar om dezelfde knoop te vragen.

\subparagraph{Aan de gebruiker toelaten tijdens de uitvoering van zijn zelfgeschreven algoritme commentaar te geven op de gevolgde stappen en dit weer te geven.}
Hier is aan voldaan.


\section{Opmerkingen}
Tot slot zijn er nog enkele opmerkingen om over dit project te maken. Bijvoorbeeld door het gebruik van de \class{ActionCommunicator} is getracht de link tussen de GUI en de core zo los mogelijk te houden. Echter, deze klasse zelf maakt gebruik van Qt om signalen te verzenden. Indien het werkelijk van belang had geweest om gemakkelijk een andere GUI te maken, had bijvoorbeeld een virtuele klasse \class{ActionCommunicatorBase} voorzien moeten zijn en in de core gebruikt. Ook wordt de classe \class{InputWidget} direct door de core klasse \class{Algorithm} gebruikt. Dit is echter niet van groot praktisch belang.



%-------------------------------------------------------------------------------------------------------------------------------------------
\begin{thebibliography}{9}
\bibitem{cursus}
	Prof. dr. Marc Gyssens,
	\emph{Algoritmen en datastructuren in ICT}.
	Universiteit Hasselt,
	2008-2009.
\bibitem{complexiteit}
	Michael Sipser,
	\emph{Introduction to the Theory of Computation}.
	Thomson Course Technology,
	Second Edition,
	International Edition,
	2006.
\bibitem{qt:download}
	qt.nokia.com/downloads/ (\today)
\bibitem{graphviz:download}
	www.graphviz.org/Download.php (\today)
\bibitem{graphviz:dot}
	www.graphviz.org/content/dot-language (\today)
\bibitem{reversedelete}
	en.wikipedia.org/wiki/Reverse-delete\_algorithm (\today)
\bibitem{boruvka}
	en.wikipedia.org/wiki/Boruvka's\_algorithm (\today)
\end{thebibliography}

\appendix
\chapter{Opbouwen van graaf in tekstformaat}\label{Appendix:File}
In dit appendix zal een beknopt voorbeeld gegeven worden van hoe een graaf gedefini\"eerd kan worden in een tekstformaat. Dit wordt getoond in listing~\ref{Code:File}. Tot slot wordt het resultaat getoond in figuur~\ref{File:Example}.
\begin{lstlisting}[caption={Inladen van bestand}, label={Code:File}]
//gerichte graaf
directed=true

//Maak enkele knopen aan
Node(0)
Node(1)
Node(2)
Node(3)
Node(4)
//Verbind deze in een cirkel
Edge(0,1)
Edge(1,2)
Edge(2,3)
Edge(3,4)
Edge(4,0)
//Meer knopen
Node(5)
Node(6)
Node(7)
Node(8)
Node(9)
//Weer verbinden
Edge(5,6)
Edge(6,7)
Edge(7,8)
Edge(8,9)
Edge(9,5)
//Verbind beide cirkels
Edge(0,5)
Edge(1,6)
Edge(2,7)
Edge(3,8)
Edge(4,9)
\end{lstlisting}

\ctable[pos=h!t, figure, botcap, caption={Resultaat}, label={File:Example}]{c}{}{\includegraphics[scale=.35]{images/example_graph2.png}}

\chapter{Opbouwen van graaf in xml}\label{Appendix:Xml}
In dit appendix zal een beknopt voorbeeld gegeven worden van hoe een graaf in xml gedefini\"eerd kan worden. De inhoud van een dergelijke file wordt getoond in listing~\ref{Code:Xml} en het resultaat wordt getoond in figuur~\ref{Xml:Example}.

\begin{lstlisting}[label={Code:Xml}, caption={Inladen van xml}, language={xml}]
<?xml version="1.0"?> 

<graph directed="false">
	<node identifier="0" label="0.0, 3.0"/>
	<node identifier="1" label="0.0, 4.0"/>
	<node identifier="2" label="0.0, 2.0"/>
	<node identifier="3" label="1.0, 4.0"/>
	<node identifier="4" label="1.0, 2.0"/>
	<node identifier="5" label="2.0, 4.0"/>
	<node identifier="6" label="3.0, 4.0"/>
	<node identifier="7" label="3.0, 3.0"/>
	<node identifier="8" label="3.0, 2.0"/>
	<node identifier="9" label="3.0, 1.0"/>
	<node identifier="10" label="3.0, 0.0"/>
	<node identifier="11" label="1.0, 1.0"/>
	<edge from="0" to ="1" label="1.0"/>
	<edge from="0" to ="2" label="1.0"/>
	<edge from="2" to ="4" label="1.0"/>
	<edge from="1" to ="3" label="1.0"/>
	<edge from="3" to ="5" label="1.0"/>
	<edge from="5" to ="6" label="1.0"/>
	<edge from="5" to ="7" label="1.42"/>
	<edge from="6" to ="7" label="1.0"/>
	<edge from="7" to ="8" label="1.0"/>
	<edge from="8" to ="9" label="1.0"/>
	<edge from="8" to ="11" label="2.24"/>
	<edge from="9" to ="10" label="1.0"/>
	<edge from="9" to ="11" label="2.0"/>
	<edge from="10" to ="11" label="2.24"/>
</graph>
\end{lstlisting}

\ctable[pos=h!t, figure, botcap, caption={Resultaat}, label={Xml:Example}]{c}{}{\includegraphics[scale=.5]{images/example_graph3.png}}

\chapter{Doxygen documentatie}\label{Appendix:Doxygen}

\includepdf[pages=-]{../doxygen/latex/refman.pdf}

\end{document}
